Structure and coloring of graphs with only small odd cycles

In this paper we investigate the role that odd cycles play in graph structure and in graph coloring. We focus on graphs with only small odd cycles and examine how the absence of large odd cycles affects graph structure. For a number of classes of such graphs, we provide full structural characterizations. Based on this structural analysis, we develop efficient and optimal graph coloring algorithms. For example, for graphs whose only odd cycles are 3-cycles and 5-cycles, we show how to color them optimally using 3, 4, 5, or 6 colors in O(E) time.