Geodesic
Choosability with separation of cycles and outerplanar graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 743-760

Voir la notice de l'article provenant de la source Library of Science

We consider the following list coloring with separation problem of graphs. Given a graph G and integers a,b, find the largest integer c such that for any list assignment L of G with |L(v)|≤ a for any vertex v and |L(u)∩ L(v)|≤ c for any edge uv of G, there exists an assignment φ of sets of integers to the vertices of G such that φ(u) ⊂ L(u) and |φ(v)|=b for any vertex v and φ(u)∩φ(v)=∅ for any edge uv. Such a value of c is called the separation number of (G,a,b). We also study the variant called the free-separation number which is defined analogously but assuming that one arbitrary vertex is precolored. We determine the separation number and free-separation number of the cycle and derive from them the free-separation number of a cactus. We also present a lower bound for the separation and free-separation numbers of outerplanar graphs of girth g≥ 5.
Keywords: coloring, choosability, outerplanar graph 
@article{DMGT_2023_43_3_a10,
     author = {Godin, Jean-Christophe and Togni, Oliver},
     title = {Choosability with separation of cycles and outerplanar graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {743--760},
     publisher = {mathdoc},
     volume = {43},
     number = {3},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a10/}
}
TY  - JOUR
AU  - Godin, Jean-Christophe
AU  - Togni, Oliver
TI  - Choosability with separation of cycles and outerplanar graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 743
EP  - 760
VL  - 43
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a10/
LA  - en
ID  - DMGT_2023_43_3_a10
ER  - 
%0 Journal Article
%A Godin, Jean-Christophe
%A Togni, Oliver
%T Choosability with separation of cycles and outerplanar graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 743-760
%V 43
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a10/
%G en
%F DMGT_2023_43_3_a10
Godin, Jean-Christophe; Togni, Oliver. Choosability with separation of cycles and outerplanar graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 743-760. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a10/