---
_id: '10129'
abstract:
- lang: eng
  text: There are many hard conjectures in graph theory, like Tutte's 5-flow conjecture,
    and the 5-cycle double cover conjecture, which would be true in general if they
    would be true for cubic graphs. Since most of them are trivially true for 3-edge-colorable
    cubic graphs, cubic graphs which are not 3-edge-colorable, often called snarks,
    play a key role in this context. Here, we survey parameters measuring how far
    apart a non 3-edge-colorable graph is from being 3-edge-colorable. We study their
    interrelation and prove some new results. Besides getting new insight into the
    structure of snarks, we show that such  measures give partial results with respect
    to these important conjectures. The paper closes with a list of open problems
    and conjectures.
article_number: P4.54
article_type: original
author:
- first_name: M. A.
  full_name: Fiol, M. A.
  last_name: Fiol
- first_name: Guiseppe
  full_name: Mazzuoccolo, Guiseppe
  last_name: Mazzuoccolo
- first_name: Eckhard
  full_name: Steffen, Eckhard
  id: '15548'
  last_name: Steffen
citation:
  ama: Fiol MA, Mazzuoccolo G, Steffen E. Measures of Edge-Uncolorability of Cubic
    Graphs. <i>The Electronic Journal of Combinatorics</i>. 2018;25(4).
  apa: Fiol, M. A., Mazzuoccolo, G., &#38; Steffen, E. (2018). Measures of Edge-Uncolorability
    of Cubic Graphs. <i>The Electronic Journal of Combinatorics</i>, <i>25</i>(4).
  bibtex: '@article{Fiol_Mazzuoccolo_Steffen_2018, title={Measures of Edge-Uncolorability
    of Cubic Graphs}, volume={25}, number={4P4.54}, journal={The Electronic Journal
    of Combinatorics}, author={Fiol, M. A. and Mazzuoccolo, Guiseppe and Steffen,
    Eckhard}, year={2018} }'
  chicago: Fiol, M. A., Guiseppe Mazzuoccolo, and Eckhard Steffen. “Measures of Edge-Uncolorability
    of Cubic Graphs.” <i>The Electronic Journal of Combinatorics</i> 25, no. 4 (2018).
  ieee: M. A. Fiol, G. Mazzuoccolo, and E. Steffen, “Measures of Edge-Uncolorability
    of Cubic Graphs,” <i>The Electronic Journal of Combinatorics</i>, vol. 25, no.
    4, 2018.
  mla: Fiol, M. A., et al. “Measures of Edge-Uncolorability of Cubic Graphs.” <i>The
    Electronic Journal of Combinatorics</i>, vol. 25, no. 4, P4.54, 2018.
  short: M.A. Fiol, G. Mazzuoccolo, E. Steffen, The Electronic Journal of Combinatorics
    25 (2018).
date_created: 2019-06-05T09:59:10Z
date_updated: 2022-01-06T06:50:30Z
department:
- _id: '542'
intvolume: '        25'
issue: '4'
keyword:
- Cubic graph
- Tait coloring
- Snark
- Boole coloring
- Berge's conjecture
- Tutte's 5-flow conjecture
language:
- iso: eng
publication: The Electronic Journal of Combinatorics
status: public
title: Measures of Edge-Uncolorability of Cubic Graphs
type: journal_article
user_id: '15540'
volume: 25
year: '2018'
...