English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Erd\H{o}s and Simonovits asked the following question: For an integer $r\geq2$ and a family of non-bipartite graphs $\mathcal{H}$, what is the tight boundof $\alpha$ such that any $\mathcal{H}$-free $n$-vertex graph with minimumdegree at least $\alpha n$ has chromatic number at most $r$? We answer thisquestion for $r=2$ and any family of odd cycles. Let $l\le k$ and $n\ge1000k^{8}$ be positive integers. Let ${\mathcal C}$ be a family of odd cycles,$C_{2l+1}$ be the shortest odd cycle not in ${\mathcal C}$, and $C_{2k+1}$ bethe longest odd cycle in ${\mathcal C}$. Let $BC_{2l+1}(n)$ denote the graphobtained by taking $2l+1$ vertex-disjoint copies of$K_{\frac{n}{2(2l+1)},\frac{n}{2(2l+1)}}$ and selecting a vertex in each ofthem such that these vertices form a cycle of length $2l+1$. Let $C_{2k+3}({n\over 2k+3})$ denote the balanced blow up of $C_{2k+3}$ with $n$ vertices. Notethat both $BC_{2l+1}(n)$ and $C_{2k+3}({n \over 2k+3})$ are $n$-vertex${\mathcal C}$-free non-bipartite graphs. We show that if $G$ is an $n$-vertex${\mathcal C}$-free graph with $\delta(G)>\max\{ \frac{n}{2(2l+1)},\frac{2}{2k+3}n\}$, then $G$ is bipartite. The bound is tight evident by$BC_{2l+1}(n)$ and $C_{2k+3}({n \over 2k+3})$. Moreover, the only $n$-vertex${\mathcal C}$-free non-bipartite graph with minimum degree $\max\{\frac{n}{2(2l+1)}, \frac{2}{2k+3}n\}=\frac{n}{2(2l+1)}$ is $BC_{2l+1}(n)$, andthe the only $n$-vertex ${\mathcal C}$-free non-bipartite graph with minimumdegree $\max\{ \frac{n}{2(2l+1)}, \frac{2}{2k+3}n\}=\frac{2}{2k+3}n$ is$C_{2k+3}({n \over 2k+3})$. Our result also unifies stability results ofAndr\'{a}sfai, Erd\H{o}s and S\'{o}s, H\"{a}ggkvist and Yuan and Peng for large$n$.

Degree stability of graphs forbidding odd cycles