Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T01:00:10.599Z Has data issue: false hasContentIssue false
  • English
  • Français

Separation Choosability and Dense Bipartite Induced Subgraphs

Part of: Graph theory

Published online by Cambridge University Press:  26 February 2019

Louis Esperet ,
Ross J. Kang  and
Stéphan Thomassé
Louis Esperet
Affiliation:
Université Grenoble Alpes, CNRS, G-SCOP, 46 Avenue Félix Viallet, 38000 Grenoble, France
Ross J. Kang*
Affiliation:
Radboud University Nijmegen, PO box 9010, 6500 GL Nijmegen, Netherlands
Stéphan Thomassé
Affiliation:
Laboratoire d’Informatique du Parallélisme, École Normale Supérieure de Lyon, 46 Allée d’Italie, 69364 Lyon, France
*
*Corresponding author. Email: r.kang@math.ru.nl
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We study a restricted form of list colouring, for which every pair of lists that correspond to adjacent vertices may not share more than one colour. The optimal list size such that a proper list colouring is always possible given this restriction, we call separation choosability. We show for bipartite graphs that separation choosability increases with (the logarithm of) the minimum degree. This strengthens results of Molloy and Thron and, partially, of Alon. One attempt to drop the bipartiteness assumption precipitates a natural class of Ramsey-type questions, of independent interest. For example, does every triangle-free graph of minimum degree d contain a bipartite induced subgraph of minimum degree Ω(log d) as d→∞?

MSC classification

Primary: 05C15: Coloring of graphs and hypergraphs
Secondary: 05C35: Extremal problems
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 5 , September 2019 , pp. 720 - 732
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© Cambridge University Press 2019

Footnotes

†

This research was partly supported by a Van Gogh grant, reference 35513NM.

‡

This author is partially supported by ANR Projects STINT (anr-13-bs02-0007) and GATO (anr-16-ce40-0009-01), and LabEx PERSYVAL-Lab (anr-11-labx-0025).

§

This author is partially supported by a Vidi grant (639.032.614) of the Netherlands Organisation for Scientific Research (NWO).

References

Ajtai, M., Komlós, J. and Szemerédi, E. (1980) A note on Ramsey numbers. J. Combin. Theory Ser. A 29 354–360.CrossRefGoogle Scholar
Ajtai, M., Komlós, J. and Szemerédi, E. (1981) A dense infinite Sidon sequence. European J. Combin. 2 1–11.CrossRefGoogle Scholar
Alon, N. (2000) Degrees and choice numbers. Random Struct. Alg. 16 364–368.3.0.CO;2-0>CrossRefGoogle Scholar
Alon, N. and Krivelevich, M. (1998) The choice number of random bipartite graphs. Ann. Combin. 2 291–297.CrossRefGoogle Scholar
Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, third edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley.CrossRefGoogle Scholar
Alon, N., Kostochka, A., Reiniger, B., West, D. B. and Zhu, X. (2016) Coloring, sparseness and girth. Israel J. Math. 214 315–331.CrossRefGoogle Scholar
Bohman, T. and Keevash, P. (2010) The early evolution of the H-free process. Invent. Math. 181 291–336.CrossRefGoogle Scholar
Bollobás, B. (1988) The chromatic number of random graphs. Combinatorica 8 49–55.CrossRefGoogle Scholar
Brandt, S. and Thomassé, S. (2011) Dense triangle-free graphs are four-colorable: A solution to the Erdős–Simonovits problem. Manuscript.Google Scholar
Cames van Batenburg, W., de Joannis de Verclos, R., Kang, R. J. and Pirot, F. (2018) Bipartite induced density in triangle-free graphs. arXiv:1808.02512Google Scholar
Chudnovsky, M., Kawarabayashi, K.-i. andSeymour, P. (2005) Detecting even holes. J. Graph Theory 48 85–111.CrossRefGoogle Scholar
Conforti, M., Cornuéjols, G., Kapoor, A. and Vušković, K. (2002), Even-hole-free graphs, part II: Recognition algorithm. J. Graph Theory 40 238–266.CrossRefGoogle Scholar
Davies, E., de Joannis de Verclos, R., Kang, R. J. and Pirot, F. (2018) Colouring triangle-free graphs with local list sizes. arXiv:1812.11152Google Scholar
Erdős, P., Rubin, A. L. and Taylor, H. (1980) Choosability in graphs. In Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 125–157.Google Scholar
Füredi, Z., Kostochka, A. and Kumbhat, M. (2014) Choosability with separation of complete multipartite graphs and hypergraphs. J. Graph Theory 76 129–137.CrossRefGoogle Scholar
Grimmett, G. R. and McDiarmid, C. J. H. (1975) On colouring random graphs. Math. Proc. Cambridge Philos. Soc. 77 313–324.CrossRefGoogle Scholar
Harris, D. G. (2016) Some results on chromatic number as a function of triangle count. arXiv:1604.00438Google Scholar
Havet, F. (2017) Finding more than an even hole. Manuscript.Google Scholar
Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience.CrossRefGoogle Scholar
Johansson, A. (1996) Asymptotic choice number for triangle-free graphs. Technical Report 91-5, DIMACS.Google Scholar
Johansson, A. (1996) The choice number of sparse graphs. Manuscript.Google Scholar
Kostochka, A. V. and Zhu, X. (2008) Adapted list coloring of graphs and hypergraphs. SIAM J. Discrete Math. 22 398–408.CrossRefGoogle Scholar
Kratochvíl, J., Tuza, Z. and Voigt, M. (1998) Brooks-type theorems for choosability with separation. J. Graph Theory 27 43–49.3.0.CO;2-G>CrossRefGoogle Scholar
Kratochvíl, J., Tuza, Z. and Voigt, M. (1998) Complexity of choosing subsets from color sets. Discrete Math. 191 139–148.CrossRefGoogle Scholar
Kwan, M., Letzter, S., Sudakov, B. and Tran, T. (2018) Dense induced bipartite subgraphs in triangle-free graphs. arXiv:1810.12144Google Scholar
Łuczak, T. (1991) The chromatic number of random graphs. Combinatorica 11 45–54.CrossRefGoogle Scholar
Matula, D. W. and Kučera, L. (1990) An expose-and-merge algorithm and the chromatic number of a random graph. In Random Graphs ‘87 (Karoński, M., Jaworski, J., and Ruciński, A., eds), Wiley, pp. 175–187.Google Scholar
Molloy, M. (2019) The list chromatic number of graphs with small clique number. J. Combin. Theory Ser. B 134 264–284.CrossRefGoogle Scholar
Molloy, M. and Thron, G. (2011) The adaptable choosability number grows with the choosability number. Discrete Math. 311 2268–2271.CrossRefGoogle Scholar
Radovanović, M. and Vušković, K. (2013) A class of three-colorable triangle-free graphs. J. Graph Theory 72 430–439.CrossRefGoogle Scholar
Saxton, D. and Thomason, A. (2015) Hypergraph containers. Invent. Math. 201 925–992.CrossRefGoogle Scholar
Shearer, J. B. (1995) On the independence number of sparse graphs. Random Struct. Alg. 7 269–271.CrossRefGoogle Scholar
Vizing, V. G. (1976) Coloring the vertices of a graph in prescribed colors. Diskret. Analiz 29 10.Google Scholar