






















Erdős and Simonovits asked the following question: For an integer $r\geq 2$ and a family of non-bipartite graphs $\mathcal{H}$, determine the infimum of $α$ such that any $\mathcal{H}$-free $n$-vertex graph with minimum degree at least $α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 $δ(G)>\max\{ n/(2(2\ell+1)), 2n/(2k+3)\}$, then $G$ is bipartite. Moreover, the bound of the minimum degree is tight.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。