A sufficient condition for a plane graph with maximum degree 6 to be class 1

作者：Wang Yingqian^*; Xu Lingji

来源：Discrete Applied Mathematics, 2013, 161(1-2): 307-310.

DOI：10.1016/j.dam.2012.08.011

• Planar graph conjecture
• Edge coloring
• Maximum degree

A well-known conjecture of Vizing (the planar graph conjecture) states that every plane graph with maximum degree Delta >= 6 is edge Delta-colorable. Vizing himself showed that every plane graph with maximum degree Delta >= 8 is edge Delta-colorable. Zhang [L. Zhang, Every graph with maximum degree 7 is of class 1, Graphs Combin. 16 (2000) 467-495] and Sanders and Zhao [D. P. Sanders, Y. Zhao, Planar graphs of maximum degree seven are class 1.J. Combin. Theory Set. B 83 (2001) 201-212] independently proved that every plane graph with maximum degree 7 is of class 1. i.e., edge 7-colorable. This note shows that every plane graph G with maximum degree 6 is edge 6-colorable if no vertex in G is incident with four faces of size 3.

• 出版日期2013-1
• 单位浙江师范大学