Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-23T14:32:13.517Z Has data issue: false hasContentIssue false
  • English
  • Français

On the structure of Dense graphs with bounded clique number

Part of: Graph theory

Published online by Cambridge University Press:  05 June 2020

Heiner Oberkampf  and
Mathias Schacht
Heiner Oberkampf
Affiliation:
Institut für Informatik, Universität Augsburg, Augsburg, Germany
Mathias Schacht*
Affiliation:
Fachbereich Mathematik, Universität Hamburg, Hamburg, Germany
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study structural properties of graphs with bounded clique number and high minimum degree. In particular, we show that there exists a function L = L(r,ɛ) such that every Kr-free graph G on n vertices with minimum degree at least ((2r–5)/(2r–3)+ɛ)n is homomorphic to a Kr-free graph on at most L vertices. It is known that the required minimum degree condition is approximately best possible for this result.

For r = 3 this result was obtained by Łuczak (2006) and, more recently, Goddard and Lyle (2011) deduced the general case from Łuczak’s result. Łuczak’s proof was based on an application of Szemerédi’s regularity lemma and, as a consequence, it only gave rise to a tower-type bound on L(3, ɛ). The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for L(r, ɛ) that is doubly exponential in poly(ɛ).

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05C75: Structural characterization of families of graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 5 , September 2020 , pp. 641 - 649
Check for updates
Copyright
© Cambridge University Press 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

The second author was supported by the Heisenberg Programme of the Deutsche Forschungsgemeinschaft.

References

Allen, P., Böttcher, J., Griffiths, S., Kohayakawa, Y. and Morris, R. (2013) The chromatic thresholds of graphs. Adv. Math. 235 261–295.CrossRefGoogle Scholar
Andrásfai, B., Erdős, P. and Sós, V. T. (1974) On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math. 8 205–218.CrossRefGoogle Scholar
Brandt, S. and Thomassé, S. Dense triangle-free graphs are four-colorable: A solution to the Erdős–Simonovits problem. Preprint.Google Scholar
Ebsen, O. and Schacht, M. (2017) Homomorphism thresholds for odd cycles. Combinatorica, to appear.Google Scholar
Erdős, P. and Simonovits, M. (1973) On a valence problem in extremal graph theory. Discrete Math. 5 323–334.CrossRefGoogle Scholar
Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 1087–1091.CrossRefGoogle Scholar
Goddard, W. and Lyle, J. (2011) Dense graphs with small clique number. J. Graph Theory 66 319–331.CrossRefGoogle Scholar
Häggkvist, R. (1982) Odd cycles of specified length in nonbipartite graphs. In Graph Theory (Cambridge, 1981), Vol. 62 of North-Holland Mathematics Studies, North-Holland, pp. 89–99.Google Scholar
Janson, S., Łuczak, T. and Rucinski, A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience.CrossRefGoogle Scholar
Letzter, S. and Snyder, R. (2019) The homomorphism threshold of {C 3, C 5}-free graphs. J. Graph Theory 90 83–106.CrossRefGoogle Scholar
Łuczak, T. (2006) On the structure of triangle-free graphs of large minimum degree. Combinatorica 26 489–493.CrossRefGoogle Scholar
Łuczak, T. and Thomassé, S. Coloring dense graphs via VC-dimension. Submitted.Google Scholar
Nikiforov, V. Chromatic number and minimum degree of Kr-free graphs. Preprint.Google Scholar
Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Vol. 260 of Colloq. Internat. CNRS, CNRS, pp. 399–401 (English, with French summary).Google Scholar
Thomassen, C. (2002) On the chromatic number of triangle-free graphs of large minimum degree. Combinatorica 22 591–596.CrossRefGoogle Scholar
Thomassen, C. (2007) On the chromatic number of pentagon-free graphs of large minimum degree. Combinatorica 27 241–243.CrossRefGoogle Scholar
Turán, P. (1941) Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 436–452 (Hungarian, with German summary).Google Scholar