Tight bound on the minimum degree to guarantee graphs forbidding some odd cycles to be bipartite

Abstract

Erdős and Simonovits asked the following question: For an integer $r\ge 2$ and a family of non-bipartite graphs $\mathcal{H}$, determine the infimum of $\alpha$ such that any $\mathcal{H}$-free $n$-vertex graph with minimum degree at least $\alpha n$ has chromatic number at most $r$. We answer this question for $r=2$ and any family consisting of odd cycles. Let $\mathcal{C}$ be a family of odd cycles in which $C_{2\ell +1}$ is the shortest odd cycle not in $\mathcal{C}$ and $C_{2k+1}$ is the longest odd cycle in $\mathcal{C}$, we show that if $G$ is an $n$-vertex $\mathcal{C}$-free graph with $n\ge 1000k^8$ and $\delta (G)>\max \{n/(2(2\ell +1)),2n/(2k+3)\}$, then $G$ is bipartite. Moreover, the bound of the minimum degree is tight.

17 pages

References in corpus (1)

• Graphs with large minimum degree and no small odd cycles are $3$-colourable

Cited by in corpus (1)

• Spectral extremal problems for non-bipartite graphs without odd cycles