Geodesic
1-planar graphs with girth at least 6 are (1,1,1,1)-colorable
Czechoslovak Mathematical Journal, Tome 73 (2023) no. 4, pp. 993-1006
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2023.0418-21
Classification : 05C10, 05C15, 05C99
Keywords: 1-planar graph; discharging 
@article{10_21136_CMJ_2023_0418_21,
     author = {Song, Lili and Sun, Lei},
     title = {1-planar graphs with girth at least 6 are (1,1,1,1)-colorable},
     journal = {Czechoslovak Mathematical Journal},
     pages = {993--1006},
     year = {2023},
     volume = {73},
     number = {4},
     doi = {10.21136/CMJ.2023.0418-21},
     zbl = {07790558},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2023.0418-21/}
}
TY  - JOUR
AU  - Song, Lili
AU  - Sun, Lei
TI  - 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable
JO  - Czechoslovak Mathematical Journal
PY  - 2023
SP  - 993
EP  - 1006
VL  - 73
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2023.0418-21/
DO  - 10.21136/CMJ.2023.0418-21
LA  - en
ID  - 10_21136_CMJ_2023_0418_21
ER  - 
%0 Journal Article
%A Song, Lili
%A Sun, Lei
%T 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable
%J Czechoslovak Mathematical Journal
%D 2023
%P 993-1006
%V 73
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2023.0418-21/
%R 10.21136/CMJ.2023.0418-21
%G en
%F 10_21136_CMJ_2023_0418_21
Song, Lili; Sun, Lei. 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable. Czechoslovak Mathematical Journal, Tome 73 (2023) no. 4, pp. 993-1006. doi: 10.21136/CMJ.2023.0418-21

[1] Appel, K., Haken, W.: The existence of unavoidable sets of geographically good configurations. Ill. J. Math. 20 (1976), 218-297. | DOI | MR | JFM

[2] Appel, K., Haken, W.: Every planar map is four colorable. I: Discharging. Ill. J. Math. 21 (1977), 429-490. | DOI | MR | JFM

[3] Appel, K., Haken, W., Koch, J.: Every planar map is four colorable. II: Reducibility. Ill. J. Math. 21 (1977), 491-567. | DOI | MR | JFM

[4] Bollobás, B.: Modern Graph Theory. Graduate Texts in Mathematics 184. Springer, New York (1998). | DOI | MR | JFM

[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 | JFM

[6] Borodin, O. V.: Colorings of plane graphs: A survey. Discrete Math. 313 (2013), 517-539. | DOI | MR | JFM

[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 | MR | JFM

[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 | JFM

[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 | MR | JFM

[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 | MR | JFM

[11] Fabrici, I., Madaras, T.: The structure of 1-planar graphs. Discrete Math. 307 (2007), 854-865. | DOI | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[14] Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Semin. Univ. Hamb. 29 (1965), 107-117 German. | DOI | MR | JFM

[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 | JFM

[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 | MR | JFM

[17] Steinberg, R.: On the desingularization of the unipotent variety. Invent. Math. 36 (1976), 209-224. | DOI | MR | JFM

[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 | MR | JFM

[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 | MR | JFM

[20] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). | MR | JFM

[21] Zhang, X., Liu, G.: On edge coloring of 1-planar graphs without adjacent triangles. Inf. Process. Lett. 112 (2012), 138-142. | DOI | MR | JFM

[22] Zhang, X., Liu, G.: On edge colorings of 1-planar graphs without chordal 5-cycles. Ars Comb. 104 (2012), 431-436. | MR | JFM

[23] Zhang, X., Wu, J.: On edge colorings of 1-planar graphs. Inf. Process. Lett. 111 (2011), 124-128. | DOI | MR | JFM

Cité par Sources :