Edge Colorings of Planar Graphs without 6-Cycles with Two Chords

Ling Xue, Jianliang Wu

Department of Information Engineering, Taishan Polytechnic, Tai’an, China.
School of Mathematics, Shandong University, Jinan, China.

DOI: 10.4236/ojdm.2013.32016                

Abstract

It is proved here that if a planar graph has maximum degree at least 6 and any 6-cycle contains at most one chord, then it is of class 1.

Keywords

Edge Coloring; Planar Graph; Cycle; Class 1

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. Fiorini and R. J. Wilson, “Edge-Colorings of Graphs,” In: S. Fiorini and R. J. Wilson, Eds., Edge-Colorings of Graphs, Vol. 16, Pitman, London, 1977.
[2]	H. Hind and Y. Zhao, “Edge Colorings of Graphs Embedable in a Surface of Low Genus,” Discrete Mathematics, Vol. 190, No. 1-3, 1998, pp. 107-114. doi:10.1016/S0012-365X(98)00050-8
[3]	L. Y. Miao and J. L. Wu, “Edge-Coloring Critical Graphs with High Degree,” Discrete Mathematics, Vol. 257, No. 1, 2002, pp. 169-172. doi:10.1016/S0012-365X(02)00395-3
[4]	L. M. Zhang, “Every Planar Graph with Maximum Degree 7 Is of Class 1,” Graphs and Combinatorics, Vol. 16, No. 4, 2000, pp. 467-495. doi:10.1007/s003730070009
[5]	D. P. Sanders and Y. Zhao, “Planar Graphs of Maximum Degree Seven Are Class 1,” Journal of Combinatorial Theory, Series B, Vol. 83, No. 2, 2001, pp. 202-212. doi:10.1006/jctb.2001.2047
[6]	P. Lam, J. Liu, W. Shiu and J. Wu, “Some Sufficient Conditions for a Planar Graph to Be of Class 1,” Congressus Numerantium, Vol. 136, No. 4, 1999, pp. 201- 205.
[7]	G. F. Zhou, “A Note on Graphs of Class 1,” Discrete Mathematics, Vol. 263, No. 1-3, 2003, pp. 339-345. doi:10.1016/S0012-365X(02)00793-8
[8]	Y. H. Bu and W. F. Wang, “Some Sufficient Conditions for a Planar Graph of Maximum Degree Six to Be Class 1,” Discrete Mathematics, Vol. 306, No. 13, 2006, pp. 1440-1445. doi:10.1016/j.disc.2006.03.032
[9]	W. P. Ni, “Edge Colorings of Planar Graphs with Δ = 6 without Short Cycles Contain Chords,” Journal of Nanjing Normal University, Vol. 34, No. 3, 2011, pp. 19-24 (in Chinese).