Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
improper coloring; 1-planar graph; discharging method
improper coloring; 1-planar graph; discharging method
Summary:
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] Appel, K., Haken, W.: The existence of unavoidable sets of geographically good configurations. Ill. J. Math. 20 (1976), 218-297. DOI 10.1215/ijm/1256049898 | MR 0392641 | Zbl 0322.05141
[2] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. North-Holland, New York (1976). MR 0411988
[3] Borodin, O. V.: Solution of Ringel's problems concerning the vertex-faced coloring of planar graphs and the coloring of 1-planar graphs. Metody Diskretn. Anal. 41 Russian (1984), 12-26. MR 0832128 | Zbl 0565.05027
[4] Borodin, O. V.: 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] Borodin, O. V., Kostochka, A. V.: 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] Borodin, O. V., Kostochka, A. V., Raspaud, A., Sopena, E.: 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] Borodin, O. V., Kostochka, A., Yancey, M.: 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] Chang, G., Havet, F., Montassier, M., Raspaud, A.: Steinberg's conjecture and near colorings. Available at http://hal.inria.fr/inria-00605810/en/
[9] Chen, Z.-Z., Kouno, M.: 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] Chen, M., Wang, Y., Liu, P., Xu, J.: 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] Cohen-Addad, V., Hebdige, M., Král', D., Li, Z., Salgado, E.: 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] Fabrici, I., Madaras, T.: 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] Hudák, D., Madaras, T.: 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] Hudák, D., Madaras, T.: 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] Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Semin. Univ. Hamb. 29 German (1965), 107-117. DOI 10.1007/BF02996313 | MR 0187232 | Zbl 0132.20701
[16] Song, W.-Y., Miao, L.-Y., Zhang, S.-J.: 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] Suzuki, Y.: 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] Zhang, X., Liu, G.: 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] Zhang, X., Liu, G.: On edge colorings of 1-planar graphs without chordal 5-cycles. Ars Comb. 104 (2012), 431-436. MR 2951804 | Zbl 1274.05186
[20] Zhang, X., Liu, G. Z., Wu, J. L.: Edge coloring of triangle-free 1-planar graphs. J. Shandong Univ., Nat. Sci. 45 Chinese (2010), 15-17. MR 2778949 | Zbl 1240.05125
[21] Zhang, X., Wu, J., Liu, G.: 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
Search
Partner of
