pith. sign in

arxiv: 1602.03904 · v2 · pith:DHNISXQ2new · submitted 2016-02-11 · 🧮 math.CO

On the structure of graphs with given odd girth and large minimum degree

classification 🧮 math.CO
keywords degreeminimumgirthfracgraphgraphsaggkvistbigger
0
0 comments X
read the original abstract

We study minimum degree conditions for which a graph with given odd girth has a simple structure. For example, the classical work of Andr\'asfai, Erd\H os, and S\'os implies that every $n$-vertex graph with odd girth $2k+1$ and minimum degree bigger than $\frac{2}{2k+1}n$ must be bipartite. We consider graphs with a weaker condition on the minimum degree. Generalizing results of H\"aggkvist and of H\"aggkvist and Jin for the cases $k=2$ and $3$, we show that every $n$-vertex graph with odd girth $2k+1$ and minimum degree bigger than $\frac{3}{4k}n$ is homomorphic to the cycle of length $2k+1$. This is best possible in the sense that there are graphs with minimum degree $\frac{3}{4k}n$ and odd girth $2k+1$ which are not homomorphic to the cycle of length $2k+1$. Similar results were obtained by Brandt and Ribe-Baumann.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.