Article in volume
Authors:
Jean-Christophe Godin
Institut de Math ́ematiques de Toulon, Universit ́e de Toulon
email: godinjeanchri@yahoo.fr
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
PDFSource:
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:
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - R. Škrekovski, A note on choosability with separation for planar graphs, Ars Combin. 58 (2001) 169–174.
Close