Remarks on planar edge-chromatic critical graphs

详细信息    查看全文

• 作者：Ligang Jin ; ^{ligang@mail.upb.de" class="auth_mail" title="E-mail the corresponding author} ; Yingli Kang¹ ; ^{yingli@mail.upb.de" class="auth_mail" title="E-mail the corresponding author} ; Eckhard Steffen ^{es@upb.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Planar graph ; Edge coloring ; Vizing&rsquo ; s conjecture ; Critical graph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 February 2016
• 年：2016
• 卷：200
• 期：Complete
• 页码：200-202
• 全文大小：327 K

文摘

The only open case of Vizing’s conjecture that every planar graph with 47a2cf" title="Click to view the MathML source">Δ≥6$\Delta \ge 6$ is a class 1 graph is Δ=6$\Delta =6$. We give a short proof of the following statement: there is no 6-critical plane graph a20b4b272f" title="Click to view the MathML source">G$G$, such that every vertex of a20b4b272f" title="Click to view the MathML source">G$G$ is incident to at most three 3-faces. A stronger statement without restriction to critical graphs is stated in Wang and 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$k$-face (k∈{3,4})$(k\in \{3,4\})$.

For Δ=5$\Delta =5$ our result gives insights into the structure of planar 5-critical graphs, and the result for Δ=6$\Delta =6$ gives support for the truth of Vizing’s planar graph conjecture.