Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421198 | Discrete Applied Mathematics | 2013 | 4 Pages |
Abstract
A well-known conjecture of Vizing (the planar graph conjecture) states that every plane graph with maximum degree Δ≥6Δ≥6 is edge ΔΔ-colorable. Vizing himself showed that every plane graph with maximum degree Δ≥8Δ≥8 is edge ΔΔ-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 Ser. 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 GG with maximum degree 6 is edge 6-colorable if no vertex in GG is incident with four faces of size 3.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yingqian Wang, Lingji Xu,