On list coloring with separation of the complete graph and set system intersections

Jean-Christophe Godin, Rémi GRISOT, Olivier TOGNI

Abstract


We consider the following list coloring with separation problem: 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 u and φ(u)∩φ(v)=∅ for any edge uv. Such a value of c is called the separation number of (G, a, b). Using a special partition of a set of lists for which we obtain an improved version of Poincaré’s crible, we determine the separation number of the complete graph Kn for some values of a, b and n, and prove bounds for the remaining values.

Keywords


graph; coloring; choosability; separation; set system

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2025.13.1.5

References

Y. Aubry, J.C. Godin, and O. Togni, Every triangle-free induced subgraph of the triangular lattice is (5m, 2m)-choosable, Discrete Applied Mathematics 166 (2014), 51–58.

Y. Aubry, J.C. Godin, and O. Togni, Free choosability of outerplanar graphs, Graphs and Combinatorics, 32(3) (2016), 851–859.

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 and Combinatorics 33 (2017),751–787.

M. Chen, K.W. Lih, and W. Wang, On choosability with separation of planar graphs without adjacent short cycles, Bulletin of the Malaysian Mathematical Sciences Society, 41 (2018), 1507–1518.

M. Chen, Y. Fan, A. Raspaud, W.C. Shiu, and W. Wang, Choosability with separation of planar graphs without prescribed cycles, Applied Mathematics and Computation, 367 (2020).

I. Choi, B. Lidický, and D. Stolee, On choosability with separation of planar graphs with forbidden cycles, Journal of Graph Theory, 81 (2016), 283–306.

M. Chen, Y. Fan, Y. Wang, and W. Wang, A sufficient condition for planar graphs to be (3,1)-choosable, Journal of Combinatorial Optimization, 34 (2017), 987–1011.

M.M. Cropper, J.L. Goldwasser, A.J.W. Hilton, D.G. Hoffman, and P.D. Johnson, Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs, Journal of Graph Theory 33(4) (2000), 199–219.

Z. Dvořák, S. Norin, and L. Postle, List coloring with requests, Journal of Graph Theory, 92 (2019), 191–206.

L. Esperet, R.J. Kang, and S. Thomassé Separation Choosability and Dense Bipartite Induced Subgraphs, Combinatorics, Probability and Computing, 28 (2019), 720–732.

Z. Füredi, A. Kostochka, and M. Kumbhat Choosability with separation of complete multipartite graphs and hypergraphs, Journal of Graph Theory, 76 (2014), 129–137.

J.C. Godin and O. Togni Choosability with Separation of cycles and outerplanar graphs, Discussiones Mathathematicae - Graph Theory, 43(3) (2023).

H.A. Kierstead and B. Lidický, On choosability with separation of planar graphs with lists of different sizes, Discrete Mathematics 338(10) (2015), 1779–1783.

J. Kratochvíl, Z. Tuza, and M. Voigt, Complexity of choosing subsets from color sets, Discrete Mathematics, 191(1-3) (1998), 139–148. J.

Kratochvíl, Z. Tuza, and M. Voigt Brooks-type theorems for choosability with separation, Journal of Graph Theory, 27 (1998), 43–49.

M. Kumbhat, K. Moss, and D. Stolee, Choosability with union separation, Discrete Mathematics 341(3) (2018), 600–605.

Y-C. Liang, T-L. Wong, and X. Zhu, Total weight choosability for Halin graphs, Electronic Journal of Graph Theory and Applications, 9(1) (2021).

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

X. Zhu, List 4-colouring of planar graphs, Journal of Combinatorial Theory, Series B 162 (2023), 1–12.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats