| Title:
|
1-planar graphs with girth at least 6 are (1,1,1,1)-colorable (English) |
| Author:
|
Song, Lili |
| Author:
|
Sun, Lei |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
73 |
| Issue:
|
4 |
| Year:
|
2023 |
| Pages:
|
993-1006 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
A graph is 1-planar if it can be drawn in the Euclidean plane so that each edge is crossed by at most one other edge. A 1-planar graph on $n$ vertices is optimal if it has $4n-8$ edges. We prove that 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable (in the sense that each of the four color classes induces a subgraph of maximum degree one). Inspired by the decomposition of 1-planar graphs, we conjecture that every 1-planar graph is (2,2,2,0,0)-colorable. (English) |
| Keyword:
|
1-planar graph |
| Keyword:
|
discharging |
| MSC:
|
05C10 |
| MSC:
|
05C15 |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 07790558 |
| DOI:
|
10.21136/CMJ.2023.0418-21 |
| . |
| Date available:
|
2023-11-23T12:19:13Z |
| Last updated:
|
2026-01-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/151943 |
| . |
| 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] Appel, K., Haken, W.: Every planar map is four colorable. I: Discharging.Ill. J. Math. 21 (1977), 429-490. Zbl 0387.05009, MR 0543795, 10.1215/ijm/1256049011 |
| Reference:
|
[3] Appel, K., Haken, W., Koch, J.: Every planar map is four colorable. II: Reducibility.Ill. J. Math. 21 (1977), 491-567. Zbl 0387.05010, MR 0543793, 10.1215/ijm/1256049012 |
| Reference:
|
[4] Bollobás, B.: Modern Graph Theory.Graduate Texts in Mathematics 184. Springer, New York (1998). Zbl 0902.05016, MR 1633290, 10.1007/978-1-4612-0619-4 |
| Reference:
|
[5] 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 (1984), 12-26 Russian. Zbl 0565.05027, MR 0832128 |
| Reference:
|
[6] Borodin, O. V.: Colorings of plane graphs: A survey.Discrete Math. 313 (2013), 517-539. Zbl 1259.05042, MR 3004485, 10.1016/j.disc.2012.11.011 |
| Reference:
|
[7] Bu, Y., Fu, C.: (1,1,0)-coloring of planar graphs without cycles of length 4 and 6.Discrete Math. 313 (2013), 2737-2741. Zbl 1280.05038, MR 3106445, 10.1016/j.disc.2013.08.005 |
| Reference:
|
[8] Chu, Y., Sun, L.: 1-planar graphs with girth at least 7 are (1,1,1,0)-colorable.J. Math. Res. Appl. 36 (2016), 643-650. Zbl 1374.05068, MR 3586296 |
| Reference:
|
[9] Cohen-Addad, V., Hebdige, M., Krá\softl, 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:
|
[10] Cowen, L. J., Cowen, R. H., Woodall, D. R.: Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency.J. Graph Theory 10 (1986), 187-195. Zbl 0596.05024, MR 0890224, 10.1002/jgt.3190100207 |
| Reference:
|
[11] 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:
|
[12] Hill, O., Smith, D., Wang, Y., Xu, L., Yu, G.: Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable.Discrete Math. 313 (2013), 2312-2317. Zbl 1281.05055, MR 3084277, 10.1016/j.disc.2013.06.009 |
| 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] Ringel, G.: Ein Sechsfarbenproblem auf der Kugel.Abh. Math. Semin. Univ. Hamb. 29 (1965), 107-117 German. Zbl 0132.20701, MR 0187232, 10.1007/BF02996313 |
| Reference:
|
[15] Song, L., Sun, L.: Every 1-planar graph without 4-cycles and adjacent 5-vertices is 5-colorable.Ars Comb. 135 (2017), 29-38. Zbl 1463.05193, MR 3702243 |
| Reference:
|
[16] Song, L., Sun, L.: 1-planar graphs without 4-cycles or 5-cycles are 5-colorable.Acta Math. Appl. Sin., Engl. Ser. 38 (2022), 169-177. Zbl 1484.05078, MR 4375781, 10.1007/s10255-022-1073-9 |
| Reference:
|
[17] Steinberg, R.: On the desingularization of the unipotent variety.Invent. Math. 36 (1976), 209-224. Zbl 0352.20035, MR 0430094, 10.1007/BF01390010 |
| Reference:
|
[18] Sun, L., Wu, J. L., Cai, H.: A totally $(\Delta+1)$-colorable 1-planar graph with girth at least five.Acta Math. Sin., Engl. Ser. 32 (2016), 1337-1349. Zbl 1359.05047, MR 3557401, 10.1007/s10114-016-5480-9 |
| Reference:
|
[19] Wang, Y., Yang, Y.: (1,0,0)-colorability of planar graphs without cycles of length 4, 5 or 9.Discrete Math. 326 (2014), 44-49. Zbl 1288.05105, MR 3188986, 10.1016/j.disc.2014.03.001 |
| Reference:
|
[20] West, D. B.: Introduction to Graph Theory.Prentice Hall, Upper Saddle River (1996). Zbl 0845.05001, MR 1367739 |
| Reference:
|
[21] Zhang, X., Liu, G.: On edge coloring 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:
|
[22] 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:
|
[23] Zhang, X., Wu, J.: On edge colorings of 1-planar graphs.Inf. Process. Lett. 111 (2011), 124-128. Zbl 1259.05050, MR 2779909, 10.1016/j.ipl.2010.11.001 |
| . |
