Research ArticleOpen AccessGoogle Scholar indexed
Edge Colorings of Planar Graphs without 6-Cycles with Two Chords
Department of Information Engineering, Taishan Polytechnic, Tai’an, China
School of Mathematics, Shandong University, Jinan, China
- 1 Department of Information Engineering, Taishan Polytechnic, Tai’an, China
- 2 School of Mathematics, Shandong University, Jinan, China
Open Journal of Discrete Mathematics·Volume 03 (2013)·Pages 83–85·Published 24 April 2013·DOI10.4236/ojdm.2013.32016
Copy link · social · email
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.
KeywordsEdge ColoringPlanar GraphCycleClass 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.
- 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
- 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
- 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
- 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
- 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.
- 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
- 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
- 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).