On the structure of almost all odd-cycle free graphs.
by
Jane Butterfield
University of Illinois at Urbana-Champaign
Coauthors: Jozsef Balogh

Determining the cardinality and describing structure of H-free graphs is well-investigated for many graphs H. If we strengthen the concept of H-free to induced subgraph containment the problem becomes different and seems to be harder; only a few precise statements are known. In the 90s, H. Prömel and A. Steger characterized the structure of almost all C₄-free, and somewhat later the structure of almost all C₅-free graphs. We extend their result, proving that almost all C_2k+1-free graphs can be covered by k vertex-disjoint cliques when k > 3 (we resolve the case of C₇ as well). Notice that this result is best possible in the sense that any graph whose vertex set can be partitioned into k classes, each spanning a complete graph, cannot contain an induced C_2k+1. This result is joint work with J. Balogh.

Date received: April 23, 2009