Face-degree bounds for planar critical graphs

zbMATH Open1344.05052MaRDI QIDQ311518FDOQ311518

Authors Eckhard Steffen, Li-Gang Jin, Yingli Kang

Publication date 13 September 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.00869

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

planar graphedge coloringcritical graphsVizing's planar graph conjecture

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: The only remaining case of a well known conjecture of Vizing states that there is no planar graph with maximum degree 6 and edge chromatic number 7. We introduce parameters for planar graphs, based on the degrees of the faces, and study the question whether there are upper bounds for these parameters for planar edge-chromatic critical graphs. Our results provide upper bounds on these parameters for smallest counterexamples to Vizing's conjecture, thus providing a partial characterization of such graphs, if they exist. For $kleq5$ the results give insights into the structure of planar edge-chromatic critical graphs.

Recommendations

• Remarks on planar edge-chromatic critical graphs
• The average degree of edge chromatic critical graphs with maximum degree seven
• Edge colorings of planar graphs without 6-cycles with three chords
• A sufficient condition for a plane graph with maximum degree 6 to be class 1
• A new sufficient condition for a planar graph of maximum degree six to be class 1

Cites work

• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• A note on graphs of class I
• A sufficient condition for a planar graph to be class I
• A sufficient condition for a plane graph with maximum degree 6 to be class 1
• Every planar graph with maximum degree 7 is of class 1
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• On critical graphs with chromatic index 4
• Planar graphs of maximum degree seven are Class I
• Some sufficient conditions for a planar graph of maximum degree six to be Class 1
• Subcubic edge-chromatic critical graphs have many edges
• The average degree of an edge-chromatic critical graph
• The size of edge chromatic critical graphs with maximum degree 6

Cited in

(4)

• The radius of \(k\)-connected planar graphs with bounded faces
• More on the structure of plane graphs with prescribed degrees of vertices, faces, edges and dual edges
• Remarks on planar edge-chromatic critical graphs
• Large faces in 4-critical planar graphs with minimum degree 4

This page was built for publication: Face-degree bounds for planar critical graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q311518)