On the Structure of Graphs with Given Odd Girth and Large Minimum Degree
Silvia Messuti, Mathias Schacht · Journal of Graph Theory · 2014
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ásfai, Erdős, and Sós implies that every n ‐vertex graph with odd girth and minimum degree bigger than must be bipartite. We consider graphs with a weaker condition on the minimum degree. Generalizing results of Häggkvist and of Häggkvist and Jin for the cases and 3, we show that every n ‐vertex graph with odd girth and minimum degree bigger than is homomorphic to the cycle of length . This is best possible in the sense that there are graphs with minimum degree and odd girth that are not homomorphic to the cycle of length . Similar results were obtained by Brandt and Ribe‐Baumann.