Geodesic
Choosability with separation of cycles and outerplanar graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 743-760 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2023},
     volume = {43},
     number = {3},
     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
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
%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/

[1] Y. Aubry, J.-C. Godin and O. Togni, Every triangle-free induced subgraph of the triangular lattice is (5m,2m)-choosable, Discrete Appl. Math. 166 (2014) 51–58. https://doi.org/10.1016/j.dam.2013.09.028

[2] Y. Aubry, J.-C. Godin and O. Togni, Free choosability of outerplanar graphs, Graphs Combin. 32 (2016) 851–859. https://doi.org/10.1007/s00373-015-1625-3

[3] Z. Berikkyzy, C. Cox, M. Dairyko, K. Hogenson, M.M Kumbhat, B. Lidický, K. Messerschmidt, K. Moss, K. Nowak, K.F. Palmowski and D. Stolee, (4, 2)-choosability of planar graphs with forbidden structures, Graphs Combin. 33 (2017) 751–787. https://doi.org/10.1007/s00373-017-1812-5

[4] M. Chen, K.-W. Lih and W. Wang, On choosability with separation of planar graphs without adjacent short cycles, Bull. Malays. Math. Sci. Soc. 41 (2018) 1507–1518. https://doi.org/10.1007/s40840-016-0409-0

[5] M. Chen, Y. Fan, A. Raspaud, W.C. Shiu and W. Wang, Choosability with separation of planar graphs without prescribed cycles, Appl. Math. Comput. 367(15) (2020) 124756. https://doi.org/10.1016/j.amc.2019.124756

[6] I. Choi, B. Lidický and D. Stolee, On choosability with separation of planar graphs with forbidden cycles, J. Graph Theory 81 (2016) 283–306. https://doi.org/10.1002/jgt.21875

[7] M. Chen, Y. Fan, Y. Wang and W. Wang, A sufficient condition for planar graphs to be (3,1)-choosable, J. Comb. Optim. 34 (2017) 987–1011. https://doi.org/10.1007/s10878-017-0124-2

[8] M.M. Cropper, J.L. Goldwasser, A.J.W. Hilton, D.G. Hoffman and P.D. Johnson Jr., Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs, J. Graph Theory 33 (2000) 199–219. https://doi.org/10.1002/(SICI)1097-0118(200004)33:43.0.CO;2-7

[9] L. Esperet, R.J. Kang and S. Thomassé, Separation choosability and dense bipartite induced subgraphs, Combin. Probab. Comput. 28 (2019) 720–732. https://doi.org/10.1017/S0963548319000026

[10] Z. Füredi, A. Kostochka and M. Kumbhat, Choosability with separation of complete multipartite graphs and hypergraphs, J. Graph Theory 76 (2014) 129–137. https://doi.org/10.1002/jgt.21754

[11] H.A. Kierstead and B. Lidický, On choosability with separation of planar graphs with lists of different sizes, Discrete Math. 338 (2015) 1779–1783. https://doi.org/10.1016/j.disc.2015.01.008

[12] J. Kratochvíl, Zs. Tuza and M. Voigt, Complexity of choosing subsets from color sets, Discrete Math. 191 (1998) 139–148. https://doi.org/10.1016/S0012-365X(98)00101-0

[13] J. Kratochvíl, Zs. Tuza and M. Voigt, Brooks-type theorems for choosability with separation, J. Graph Theory 27 (1998) 43–49. https://doi.org/10.1002/(SICI)1097-0118(199801)27:13.0.CO;2-G

[14] M. Kumbhat, K. Moss and D. Stolee, Choosability with union separation, Discrete Math. 341 (2018) 600–605. https://doi.org/10.1016/j.disc.2017.10.022

[15] R. Škrekovski, A note on choosability with separation for planar graphs, Ars Combin. 58 (2001) 169–174.