Measurements of edge-uncolorability

DOI10.1016/j.disc.2003.05.005zbMath1041.05031OpenAlexW1969424031MaRDI QIDQ1827679

Eckhard Steffen

Publication date: 6 August 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2003.05.005

zbMATH Keywords

Cubic graphsChromatic indexSnarksEdge chromatic difference sequence

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (26)

Snarks with resistance \(n\) and flow resistance \(2n\) ⋮ On snarks that are far from being 3-edge colorable ⋮ Oddness to resistance ratios in cubic graphs ⋮ On parsimonious edge-colouring of graphs with maximum degree three ⋮ Cubic Graphs with Large Circumference Deficit ⋮ 3-critical subgraphs of snarks ⋮ Girth, oddness, and colouring defect of snarks ⋮ Three measures of edge-uncolorability ⋮ Reducible 3-critical graphs ⋮ On resistance of graphs ⋮ Coverings of cubic graphs and 3-edge colorability ⋮ On disjoint matchings in cubic graphs: maximum 2-edge-colorable and maximum 3-edge-colorable subgraphs ⋮ On maximum \(k\)-edge-colorable subgraphs of bipartite graphs ⋮ Measures of edge-uncolorability of cubic graphs ⋮ Gallai's question and constructions of almost hypotraceable graphs ⋮ Weak oddness as an approximation of oddness and resistance in cubic graphs ⋮ Snarks with large oddness and small number of vertices ⋮ On disjoint matchings in cubic graphs ⋮ Small snarks with large oddness ⋮ The smallest nontrivial snarks of oddness 4 ⋮ On Sylvester Colorings of Cubic Graphs ⋮ Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 ⋮ Color-character of uncolorable cubic graphs ⋮ Parsimonious edge-coloring on surfaces ⋮ Minimal edge colorings of class 2 graphs and double graphs ⋮ Nowhere-zero flows on signed regular graphs

Cites Work

• The edge chromatic difference sequence of a cubic graph
• Classification and characterizations of snarks
• Five cycle double covers of some cubic graphs
• Parsimonious edge coloring
• Snarks without small cycles
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• A Proof of 4-Coloring the Edges of a Cubic Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Measurements of edge-uncolorability