| Title:
|
Note on improper coloring of $1$-planar graphs (English) |
| Author:
|
Chu, Yanan |
| Author:
|
Sun, Lei |
| Author:
|
Yue, Jun |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
69 |
| Issue:
|
4 |
| Year:
|
2019 |
| Pages:
|
955-968 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
improper coloring |
| Keyword:
|
1-planar graph |
| Keyword:
|
discharging method |
| MSC:
|
05C15 |
| idZBL:
|
07144867 |
| idMR:
|
MR4039612 |
| DOI:
|
10.21136/CMJ.2019.0558-17 |
| . |
| Date available:
|
2019-11-28T08:47:35Z |
| Last updated:
|
2022-01-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147906 |
| . |
| Reference:
|
[1] Appel, K., Haken, W.: The existence of unavoidable sets of geographically good configurations.Ill. J. Math. 20 (1976), 218-297. Zbl 0322.05141, MR 0392641, 10.1215/ijm/1256049898 |
| Reference:
|
[2] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications.North-Holland, New York (1976). MR 0411988 |
| Reference:
|
[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. Zbl 0565.05027, MR 0832128 |
| Reference:
|
[4] Borodin, O. V.: A new proof of the 6 color theorem.J. Graph Theory 19 (1995), 507-521. Zbl 0826.05027, MR 1333779, 10.1002/jgt.3190190406 |
| Reference:
|
[5] Borodin, O. V., Kostochka, A. V.: Defective 2-colorings of sparse graphs.J. Comb. Theory, Ser. B 104 (2014), 72-80. Zbl 1282.05041, MR 3132745, 10.1016/j.jctb.2013.10.002 |
| Reference:
|
[6] Borodin, O. V., Kostochka, A. V., Raspaud, A., Sopena, E.: Acyclic colouring of 1-planar graphs.Discrete Appl. Math. 114 (2001), 29-41. Zbl 0996.05053, MR 1865580, 10.1016/S0166-218X(00)00359-0 |
| Reference:
|
[7] Borodin, O. V., Kostochka, A., Yancey, M.: On 1-improper 2-coloring of sparse graphs.Discrete Math. 313 (2013), 2638-2649. Zbl 1281.05060, MR 3095439, 10.1016/j.disc.2013.07.014 |
| Reference:
|
[8] Chang, G., Havet, F., Montassier, M., Raspaud, A.: Steinberg's conjecture and near colorings.Available at http://hal.inria.fr/inria-00605810/en/. |
| Reference:
|
[9] Chen, Z.-Z., Kouno, M.: A linear-time algorithm for 7-coloring 1-plane graphs.Algorithmica 43 (2005), 147-177. Zbl 1082.05084, MR 2172321, 10.1007/s00453-004-1134-x |
| Reference:
|
[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. Zbl 1327.05073, MR 3431403, 10.1016/j.disc.2015.10.029 |
| Reference:
|
[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. Zbl 1350.05018, MR 3575214, 10.1016/j.jctb.2016.07.006 |
| Reference:
|
[12] Fabrici, I., Madaras, T.: The structure of 1-planar graphs.Discrete Math. 307 (2007), 854-865. Zbl 1111.05026, MR 2297168, 10.1016/j.disc.2005.11.056 |
| Reference:
|
[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. Zbl 1194.05025, MR 2574477, 10.7151/dmgt.1454 |
| Reference:
|
[14] Hudák, D., Madaras, T.: On local properties of 1-planar graphs with high minimum degree.Ars Math. Contemp. 4 (2011), 245-254. Zbl 1237.05053, MR 2802062, 10.26493/1855-3974.131.91c |
| Reference:
|
[15] Ringel, G.: Ein Sechsfarbenproblem auf der Kugel.Abh. Math. Semin. Univ. Hamb. 29 German (1965), 107-117. Zbl 0132.20701, MR 0187232, 10.1007/BF02996313 |
| Reference:
|
[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 |
| Reference:
|
[17] Suzuki, Y.: Optimal 1-planar graphs which triangulate other surfaces.Discrete Math. 310 (2010), 6-11. Zbl 1188.05056, MR 2558962, 10.1016/j.disc.2009.07.016 |
| Reference:
|
[18] Zhang, X., Liu, G.: On edge colorings of 1-planar graphs without adjacent triangles.Inf. Process. Lett. 112 (2012), 138-142. Zbl 1239.05078, MR 2876230, 10.1016/j.ipl.2011.10.021 |
| Reference:
|
[19] Zhang, X., Liu, G.: On edge colorings of 1-planar graphs without chordal 5-cycles.Ars Comb. 104 (2012), 431-436. Zbl 1274.05186, MR 2951804 |
| Reference:
|
[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. Zbl 1240.05125, MR 2778949 |
| Reference:
|
[21] Zhang, X., Wu, J., Liu, G.: List edge and list total coloring of 1-planar graphs.Front. Math. China 7 (2012), 1005-1018. Zbl 1254.05050, MR 2965951, 10.1007/s11464-012-0184-7 |
| . |
