1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Choosability with Separation of Cycles and Outerplanar Graphs

Published Online: 18 Mar 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 01 Sep 2020
Accepted: 21 Feb 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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)| ≤ 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

MSC 2010

[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. doi:10.1016/j.dam.2013.09.02810.1016/j.dam.2013.09.028Search in Google Scholar

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

[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. doi:10.1007/s00373-017-1812-510.1007/s00373-017-1812-5Search in Google Scholar

[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. doi:10.1007/s40840-016-0409-010.1007/s40840-016-0409-0Search in Google Scholar

[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 (2020) #124756. doi:10.1016/j.amc.2019.12475610.1016/j.amc.2019.124756Search in Google Scholar

[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. doi:10.1002/jgt.2187510.1002/jgt.21875Search in Google Scholar

[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. doi:10.1007/s10878-017-0124-210.1007/s10878-017-0124-2Search in Google Scholar

[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. doi:10.1002/(SICI)1097-0118(200004)33:4〈199::AID-JGT2〉3.0.CO;2-7Search in Google Scholar

[9] L. Esperet, R.J. Kang and S. Thomassé, Separation choosability and dense bipartite induced subgraphs, Combin. Probab. Comput. 28 (2019) 720–732. doi:10.1017/S096354831900002610.1017/S0963548319000026Search in Google Scholar

[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. doi:10.1002/jgt.2175410.1002/jgt.21754Search in Google Scholar

[11] H.A. Kierstead and B. Lidický, On choosability with separation of planar graphs with lists of di erent sizes, Discrete Math. 338 (2015) 1779–1783. doi:10.1016/j.disc.2015.01.00810.1016/j.disc.2015.01.008Search in Google Scholar

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

[13] J. Kratochvíl, Zs. Tuza and M. Voigt, Brooks-type theorems for choosability with separation, J. Graph Theory 27 (1998) 43–49. doi:10.1002/(SICI)1097-0118(199801)27:1〈43::AID-JGT7〉3.0.CO;2-GSearch in Google Scholar

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo