On the structure of dense graphs with bounded clique number

DOI10.1017/S0963548319000324MaRDI QIDQ4987252zbMATH OpenFDO

Authors Heiner Oberkampf, M. Schacht

Publication date 30 April 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.02302

zbMATH Keywords

3-colourable triangle-free graphschromatic threshold

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75)

Abstract: We study structural properties of graphs with fixed clique number and high minimum degree. In particular, we show that there exists a function $L=L(r,varepsilon)$, such that every $K_r$-free graph $G$ on $n$ vertices with minimum degree at least $(frac2r-52r-3+varepsilon)n$ is homomorphic to a $K_r$-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 L uczak [On the structure of triangle-free graphs of large minimum degree, Combinatorica 26 (2006), no. 4, 489-493] and, more recently, Goddard and Lyle [Dense graphs with small clique number, J. Graph Theory 66 (2011), no. 4, 319-331] deduced the general case from L uczak's result. L uczak's proof was based on an application of Szemer'edi's regularity lemma and, as a consequence, it only gave rise to a tower-type bound on $L(3,varepsilon)$. The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for $L(r,varepsilon)$ that is doubly exponential in poly($varepsilon$).

Recommendations

• Dense graphs with small clique number
• Note on the structure of graphs with bounded clique number
• Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite
• On the structure of triangle-free graphs of large minimum degree
• The typical structure of graphs with no large cliques

Cites work

• Dense graphs with small clique number
• Homomorphism thresholds for odd cycles
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• ODD Cycles of Specified Length in Non-Bipartite Graphs
• On a valence problem in extremal graph theory
• On the chromatic number of pentagon-free graphs of large minimum degree
• On the chromatic number of triangle-free graphs of large minimum degree
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the structure of linear graphs
• On the structure of triangle-free graphs of large minimum degree
• The chromatic thresholds of graphs
• The homomorphism threshold of \({C_3, C_5}\)-free graphs

Cited in

(13)

• Cliques in dense GF(\(q\))-representable matroids
• Note on the structure of graphs with bounded clique number
• Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite
• Cliques in graphs with bounded minimum degree
• Dense graphs with small clique number
• Asymptotic Structure for the Clique Density Theorem
• Minimum degree and the graph removal lemma
• The minimum degree removal lemma thresholds
• Independent sets in K₆-free graphs with large degree
• Beyond chromatic threshold via (p,q)-theorem, and blow-up phenomenon
• The minimum degree removal lemma thresholds (extended abstract)
• A criterion for Andrásfai-Erdős-Sós type theorems and applications
• A tight minimum-degree condition guaranteeing that every \(\{C_5,C_7,C_9,C_{11}\}\)-free graph is 3-colorable

This page was built for publication: On the structure of dense graphs with bounded clique number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987252)