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

Cité par Sources :