Geodesic
The structure and the list 3-dynamic coloring of outer-1-planar graphs
Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3.

Voir la notice de l'article provenant de la source Episciences

An outer-1-planar graph is a graph admitting a drawing in the plane so that all vertices appear in the outer region of the drawing and every edge crosses at most one other edge. This paper establishes the local structure of outer-1-planar graphs by proving that each outer-1-planar graph contains one of the seventeen fixed configurations, and the list of those configurations is minimal in the sense that for each fixed configuration there exist outer-1-planar graphs containing this configuration that do not contain any of another sixteen configurations. There are two interesting applications of this structural theorem. First of all, we conclude that every (resp. maximal) outer-1-planar graph of minimum degree at least 2 has an edge with the sum of the degrees of its two end-vertices being at most 9 (resp. 7), and this upper bound is sharp. On the other hand, we show that the list 3-dynamic chromatic number of every outer-1-planar graph is at most 6, and this upper bound is best possible.
DOI : 10.46298/dmtcs.5860
Classification : 05C10, 05C15 
@article{DMTCS_2021_23_3_a2,
     author = {Li, Yan and Zhang, Xin},
     title = {The structure and the list 3-dynamic coloring of outer-1-planar graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2021-2022},
     doi = {10.46298/dmtcs.5860},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5860/}
}
TY  - JOUR
AU  - Li, Yan
AU  - Zhang, Xin
TI  - The structure and the list 3-dynamic coloring of outer-1-planar graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2021-2022
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5860/
DO  - 10.46298/dmtcs.5860
LA  - en
ID  - DMTCS_2021_23_3_a2
ER  - 
%0 Journal Article
%A Li, Yan
%A Zhang, Xin
%T The structure and the list 3-dynamic coloring of outer-1-planar graphs
%J Discrete mathematics & theoretical computer science
%D 2021-2022
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5860/
%R 10.46298/dmtcs.5860
%G en
%F DMTCS_2021_23_3_a2
Li, Yan; Zhang, Xin. The structure and the list 3-dynamic coloring of outer-1-planar graphs. Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3. doi : 10.46298/dmtcs.5860. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.5860/

Cité par Sources :