Remarks on planar edge-chromatic critical graphs

DOI10.1016/J.DAM.2015.07.007zbMATH Open1329.05110arXiv1702.07559OpenAlexW950132537MaRDI QIDQ906449FDOQ906449

Authors: Eckhard Steffen, Li-Gang Jin, Yingli Kang 

Publication date: 21 January 2016

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

Abstract: The only open case of Vizing's conjecture that every planar graph with $Deltageq6$ is a class 1 graph is $Delta=6$. We give a short proof of the following statement: there is no 6-critical plane graph $G$, such that every vertex of $G$ is incident to at most three 3-faces. A stronger statement without restriction to critical graphs is stated in cite{Wang_Xu_2013}. However, the proof given there works only for critical graphs. Furthermore, we show that every 5-critical plane graph has a 3-face which is adjacent to a $k$-face $(kin3,4)$. For $Delta=5$ our result gives insights into the structure of planar $5$-critical graphs, and the result for $Delta=6$ gives support for the truth of Vizing's planar graph conjecture.

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

Recommendations

• Face-degree bounds for planar critical graphs
• 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 sufficient condition for edge 6-colorable planar graphs with maximum degree 6
• A new sufficient condition for a planar graph of maximum degree six to be class 1

zbMATH Keywords

planar graphVizing's conjecturecritical graphedge coloring

Mathematics Subject Classification ID

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

Cites Work

• Planar graphs of maximum degree seven are Class I
• The size of edge chromatic critical graphs with maximum degree 6
• 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
• The average degree of an edge-chromatic critical graph
• Chromatic-index critical multigraphs of order 20

Cited In (2)

• Face-degree bounds for planar critical graphs
• Graph edge coloring: a survey

This page was built for publication: Remarks on planar edge-chromatic critical graphs

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