# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

# Discussiones Mathematicae Graph Theory

Article in volume

Authors:

J.-C. Godin

Jean-Christophe Godin

Institut de Math ́ematiques de Toulon, Universit ́e de Toulon

email: godinjeanchri@yahoo.fr

O. Togni

Oliver Togni

Laboratoire Le2i UMR CNRS 5158 Université de Bourgogne 21078 Dijon cedex FRANCE

email: olivier.togni@u-bourgogne.fr

Title:

Choosability with separation of cycles and outerplanar graphs

Source:

Discussiones Mathematicae Graph Theory 43(3) (2023) 743-760

Received: 2020-09-01 , Revised: 2021-02-20 , Accepted: 2021-02-21 , Available online: 2021-03-05 , https://doi.org/10.7151/dmgt.2398

Abstract:

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)|\le a$ for any vertex $v$ and $|L(u)\cap L(v)|\le c$ for any edge $uv$ of $G$, there exists an assignment $\varphi$ of sets of integers to the vertices of $G$ such that $\varphi(u) \subset L(u)$ and $|\varphi(v)|=b$ for any vertex $v$ and $\varphi(u)\cap \varphi(v)=\emptyset$ 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\ge 5$.

Keywords:

coloring, choosability, outerplanar graph

References:

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:4<199::AID-JGT2>3.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:1<43::AID-JGT7>3.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.