Face-degree bounds for planar critical graphs

zbMATH Open1344.05052arXiv1501.00869MaRDI 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)

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.

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

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

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

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)

Cites Work

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

Cited In (4)

• Large faces in 4-critical planar graphs with minimum degree 4
• Remarks on planar edge-chromatic critical graphs
• 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

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)