Czechoslovak Mathematical Journal, Vol. 69, No. 4, pp. 955-968, 2019
Note on improper coloring of 1-planar graphs
Yanan Chu, Lei Sun, Jun Yue
Received December 7, 2017. Published online June 3, 2019.
Abstract: A graph $G=(V,E)$ is called improperly $(d_1, \dots, d_k)$-colorable if the vertex set $V$ can be partitioned into subsets $V_1, \dots, V_k$ such that the graph $G[V_i]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1 \leq i \leq k$. In this paper, we mainly study the improper coloring of 1-planar graphs and show that 1-planar graphs with girth at least 7 are (2,0,0,0)-colorable.
References: [1] K. Appel, W. Haken: The existence of unavoidable sets of geographically good configurations. Ill. J. Math. 20 (1976), 218-297. MR 0392641 | Zbl 0322.05141
[2] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. North-Holland, New York (1976).
[3] O. V. Borodin: Solution of Ringel's problems concerning the vertex-faced coloring of planar graphs and the coloring of 1-planar graphs. Metody Diskretn. Anal. 41 (1984), 12-26. (In Russian.) MR 0832128 | Zbl 0565.05027
[4] O. V. Borodin: A new proof of the 6 color theorem. J. Graph Theory 19 (1995), 507-521. DOI 10.1002/jgt.3190190406 | MR 1333779 | Zbl 0826.05027
[5] O. V. Borodin, A. V. Kostochka: Defective 2-colorings of sparse graphs. J. Comb. Theory, Ser. B 104 (2014), 72-80. DOI 10.1016/j.jctb.2013.10.002 | MR 3132745 | Zbl 1282.05041
[6] O. V. Borodin, A. V. Kostochka, A. Raspaud, E. Sopena: Acyclic colouring of 1-planar graphs. Discrete Appl. Math. 114 (2001), 29-41. DOI 10.1016/S0166-218X(00)00359-0 | MR 1865580 | Zbl 0996.05053
[7] O. V. Borodin, A. Kostochka, M. Yancey: On 1-improper 2-coloring of sparse graphs. Discrete Math. 313 (2013), 2638-2649. DOI 10.1016/j.disc.2013.07.014 | MR 3095439 | Zbl 1281.05060
[8] G. Chang, F. Havet, M. Montassier, A. Raspaud: Steinberg's conjecture and near colorings. Available at http://hal.inria.fr/inria-00605810/en/.
[9] Z.-Z. Chen, M. Kouno: A linear-time algorithm for 7-coloring 1-plane graphs. Algorithmica 43 (2005), 147-177. DOI 10.1007/s00453-004-1134-x | MR 2172321 | Zbl 1082.05084
[10] M. Chen, Y. Wang, P. Liu, J. Xu: Planar graphs without cycles of length 4 or 5 are (2,0,0)-colorable. Discrete Math. 339 (2016), 886-905. DOI 10.1016/j.disc.2015.10.029 | MR 3431403 | Zbl 1327.05073
[11] V. Cohen-Addad, M. Hebdige, D. Král', Z. Li, E. Salgado: Steinberg's conjecture is false. J. Comb. Theory, Ser. B 122 (2017), 452-456. DOI 10.1016/j.jctb.2016.07.006 | MR 3575214 | Zbl 1350.05018
[12] I. Fabrici, T. Madaras: The structure of 1-planar graphs. Discrete Math. 307 (2007), 854-865. DOI 10.1016/j.disc.2005.11.056 | MR 2297168 | Zbl 1111.05026
[13] D. Hudák, T. Madaras: On local structure of 1-planar graphs of minimum degree 5 and girth 4. Discuss. Math., Graph Theory 29 (2009), 385-400. DOI 10.7151/dmgt.1454 | MR 2574477 | Zbl 1194.05025
[14] D. Hudák, T. Madaras: On local properties of 1-planar graphs with high minimum degree. Ars Math. Contemp. 4 (2011), 245-254. DOI 10.26493/1855-3974.131.91c | MR 2802062 | Zbl 1237.05053
[15] G. Ringel: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Semin. Univ. Hamb. 29 (1965), 107-117. (In German.) DOI 10.1007/BF02996313 | MR 0187232 | Zbl 0132.20701
[16] W.-Y. Song, L.-Y. Miao, S.-J. Zhang: List edge and list total coloring of triangle-free 1-planar graphs. J. East China Norm. Univ. Natur. Sci. Ed. (2014), 40-44. MR 3243188
[17] Y. Suzuki: Optimal 1-planar graphs which triangulate other surfaces. Discrete Math. 310 (2010), 6-11. DOI 10.1016/j.disc.2009.07.016 | MR 2558962 | Zbl 1188.05056
[18] X. Zhang, G. Liu: On edge colorings of 1-planar graphs without adjacent triangles. Inf. Process. Lett. 112 (2012), 138-142. DOI 10.1016/j.ipl.2011.10.021 | MR 2876230 | Zbl 1239.05078
[19] X. Zhang, G. Liu: On edge colorings of 1-planar graphs without chordal 5-cycles. Ars Comb. 104 (2012), 431-436. MR 2951804 | Zbl 1274.05186
[20] X. Zhang, G. Z. Liu, J. L. Wu: Edge coloring of triangle-free 1-planar graphs. J. Shandong Univ., Nat. Sci. 45 Chinese (2010), 15-17. MR 2778949 | Zbl 1240.05125
[21] X. Zhang, J. Wu, G. Liu: List edge and list total coloring of 1-planar graphs. Front. Math. China 7 (2012), 1005-1018. DOI 10.1007/s11464-012-0184-7 | MR 2965951 | Zbl 1254.05050
Affiliations: Yanan Chu, Lei Sun (corresponding author), Jun Yue, School of Mathematics and Statistics, Shandong Normal University, No. 1, Daxue Road, Jinan, Shandong, P. R. China, e-mail: 175410001@fzu.cn, Lsun89@163.com, yuejun06@126.com
