×

zbMATH — the first resource for mathematics

On edge colorings of 1-planar graphs without 5-cycles with two chords. (English) Zbl 1409.05091
A graph is called 1-planar if it can be drawn in the plane so that each of its edges is crossed by at most one other edge. Let \(G\) be a 1-planar graph of maximum degree \(\Delta\). In this paper the following theorem is proved: If \(\Delta \geqslant 8\) and any 5-cycle of \(G\) has at most one chord, then \(G\) is edge-colorable with \(\Delta\) colors. This theorem weakens the hypotheses of a previous theorem of this type by X. Zhang and G. Z. Liu [Ars Comb. 104, 431–436 (2012; Zbl 1274.05186)]: If \(\Delta \geqslant 9\) and any 5-cycle of \(G\) has no chord at all, then \(G\) is edge-colorable with \(\Delta\) colors.
The authors use their “discharging method” which requires a case-by-case analysis based on V. G. Vizing’s adjacency lemma [Russ. Math. Surv. 23, No. 6, 125–141 (1968; Zbl 0192.60502); translation from Usp. Mat. Nauk 23, No. 6(144), 117–134 (1968)].
Notice that in the 1-planar case, the condition \(\Delta \geqslant 8\) is not a necessary one; for example, the complete four-partite graph \(K_{2,2,2,2}\) is 1-planar and is edge-colorable with \(\Delta = 6\) colors.
MSC:
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C76 Graph operations (line graphs, products, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (MacMillan, London, 1976). · Zbl 1226.05083
[2] Y.H. Bu and W.F. Wang, Some sufficient conditions for a planar graph of maximum degree six to be Class 1, Discrete Math. 306 (2006) 1440-1445. doi:10.1016/j.disc.2006.03.032 · Zbl 1095.05014
[3] P. Erdős and R.J. Wilson, On the chromatic index of almost all graphs, J. Combin. Theory Ser. B 23 (1977) 255-257. doi:10.1016/0095-8956(77)90039-9
[4] R. Luo, L.Y. Miao and Y. Zhao, The size of edge chromatic critical graphs with maximum degree 6, J. Graph Theory 60 (2009) 149-171. doi:10.1002/jgt.20351 · Zbl 1247.05083
[5] S. Fiorini and R.J. Wilson, Edge-colorings of graphs, in: Research Notes in Mathematics 16 (Pitman, London, 1977). · Zbl 0435.05024
[6] W.P. Ni, Edge colorings of planar graphs with ∆ = 6 without short cycles contain chords, J. Nanjing Norm. Univ. Nat. Sci. Ed. 34 (2011) 19-24.
[7] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107-117. · Zbl 0132.20701
[8] D.P. Sanders and Y. Zhao, Planar graphs of maximum degree seven are Class I, J. Combin. Theory Ser. B 83 (2001) 201-212. doi:10.1006/jctb.2001.2047 · Zbl 1024.05031
[9] V.G. Vizing, Critical graphs with given chromatic class, Diskret. Analiz 5 (1965) 9-17.
[10] V.G. Vizing, Some unsolved problems in graph theory, Russian Math. Surveys 23 (1968) 125-141. doi:10.1070/RM1968v023n06ABEH001252
[11] L. Xue and J.L. Wu, Edge colorings of planar graphs without 6-cycles with two chords, Open J. Discrete Math. 3 (2013) 83-85. doi:10.4236/ojdm.2013.32016 · Zbl 1370.05075
[12] J.-L. Wu and L. Xue, Edge colorings of planar graphs without 5-cycles with two chords, Theoret. Comput. Sci. 518 (2014) 124-127. doi:10.1016/j.tcs.2013.07.027 · Zbl 1370.05075
[13] L.M. Zhang, Every planar graph with maximum degree 7 is of Class 1, Graphs Combin. 16 (2000) 467-495. doi:10.1007/s003730070009 · Zbl 0988.05042
[14] X. Zhang, Class two 1-planar graphs with maximum degree six or seven (2011). arXiv: 1104.4687
[15] X. Zhang and J.-L. Wu, On edge colorings of 1-planar graphs, Inform. Process. Lett. 111 (2011) 124-128. doi:10.1016/j.ipl.2010.11.001 · Zbl 1259.05050
[16] X. Zhang and G.Z. Liu, On edge colorings of 1-planar graphs without adjacent triangles, Inform. Process. Lett. 112 (2012) 138-142. doi:10.1016/j.ipl.2011.10.021 · Zbl 1239.05078
[17] X. Zhang and G.Z. Liu, On edge colorings of 1-planar graphs without chordal 5-cycles, Ars Combin. 104 (2012) 431-436. · Zbl 1274.05186
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.