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


J.-C. Godin

Jean-Christophe Godin

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


O. Togni

Oliver Togni

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




Choosability with separation of cycles and outerplanar graphs



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 ,


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$.


coloring, choosability, outerplanar graph


  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.
  2. Y. Aubry, J.-C. Godin and O. Togni, Free choosability of outerplanar graphs, Graphs Combin. 32 (2016) 851–859.
  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.
  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.
  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.
  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.
  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.
  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.<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.
  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.
  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.
  12. J. Kratochvíl, Zs. Tuza and M. Voigt, Complexity of choosing subsets from color sets, Discrete Math. 191 (1998) 139–148.
  13. J. Kratochvíl, Zs. Tuza and M. Voigt, Brooks-type theorems for choosability with separation, J. Graph Theory 27 (1998) 43–49.<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.
  15. R. Škrekovski, A note on choosability with separation for planar graphs, Ars Combin. 58 (2001) 169–174.