Article ID Journal Published Year Pages File Type
421198 Discrete Applied Mathematics 2013 4 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,