episciences.org_5860_1653753839
1653753839
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
08
27
2021
vol. 23, no. 3
Graph Theory
The structure and the list 3dynamic coloring of outer1planar graphs
Yan
Li
Xin
Zhang
An outer1planar 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
outer1planar graphs by proving that each outer1planar 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
outer1planar 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)
outer1planar graph of minimum degree at least 2 has an edge with the sum of
the degrees of its two endvertices being at most 9 (resp. 7), and this upper
bound is sharp. On the other hand, we show that the list 3dynamic chromatic
number of every outer1planar graph is at most 6, and this upper bound is best
possible.
08
27
2021
5860
arXiv:1910.09419
10.48550/arXiv.1910.09419
https://arxiv.org/abs/1910.09419v2
https://arxiv.org/abs/1910.09419v1
10.46298/dmtcs.5860
https://dmtcs.episciences.org/5860

https://dmtcs.episciences.org/8381/pdf