Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
1-planar graph; discharging
1-planar graph; discharging
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.
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] Appel, K., Haken, W.: Every planar map is four colorable. I: Discharging. Ill. J. Math. 21 (1977), 429-490. DOI 10.1215/ijm/1256049011 | MR 0543795 | Zbl 0387.05009
[3] Appel, K., Haken, W., Koch, J.: Every planar map is four colorable. II: Reducibility. Ill. J. Math. 21 (1977), 491-567. DOI 10.1215/ijm/1256049012 | MR 0543793 | Zbl 0387.05010
[4] Bollobás, B.: Modern Graph Theory. Graduate Texts in Mathematics 184. Springer, New York (1998). DOI 10.1007/978-1-4612-0619-4 | MR 1633290 | Zbl 0902.05016
[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. MR 0832128 | Zbl 0565.05027
[6] Borodin, O. V.: Colorings of plane graphs: A survey. Discrete Math. 313 (2013), 517-539. DOI 10.1016/j.disc.2012.11.011 | MR 3004485 | Zbl 1259.05042
[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. DOI 10.1016/j.disc.2013.08.005 | MR 3106445 | Zbl 1280.05038
[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. MR 3586296 | Zbl 1374.05068
[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. DOI 10.1016/j.jctb.2016.07.006 | MR 3575214 | Zbl 1350.05018
[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. DOI 10.1002/jgt.3190100207 | MR 0890224 | Zbl 0596.05024
[11] 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
[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. DOI 10.1016/j.disc.2013.06.009 | MR 3084277 | Zbl 1281.05055
[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] Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Semin. Univ. Hamb. 29 (1965), 107-117 German. DOI 10.1007/BF02996313 | MR 0187232 | Zbl 0132.20701
[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. MR 3702243 | Zbl 1463.05193
[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. DOI 10.1007/s10255-022-1073-9 | MR 4375781 | Zbl 1484.05078
[17] Steinberg, R.: On the desingularization of the unipotent variety. Invent. Math. 36 (1976), 209-224. DOI 10.1007/BF01390010 | MR 0430094 | Zbl 0352.20035
[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. DOI 10.1007/s10114-016-5480-9 | MR 3557401 | Zbl 1359.05047
[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. DOI 10.1016/j.disc.2014.03.001 | MR 3188986 | Zbl 1288.05105
[20] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). MR 1367739 | Zbl 0845.05001
[21] Zhang, X., Liu, G.: On edge coloring 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
[22] 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
[23] Zhang, X., Wu, J.: On edge colorings of 1-planar graphs. Inf. Process. Lett. 111 (2011), 124-128. DOI 10.1016/j.ipl.2010.11.001 | MR 2779909 | Zbl 1259.05050
Search
Partner of
