Article
| 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 |
| DOI: | 10.21136/CMJ.2023.0418-21 |
| . | |
| Date available: | 2023-11-23T12:19:13Z |
| Last updated: | 2023-11-27 |
| 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 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
