Question

Let G be a graph in which there is a cycle C odd length that has vertices on all of the other odd cycles. Prove that the chromatic number of G is less than or equal to 5.

Answer 1

Solution:

Let C be the smallest odd cycle in G. Note that C has no chords (i.e. edges between its vertices that aren't part of the cycle), as otherwise there would be a smaller odd cycle. Hence we can color C with 3 colors, and it will be a valid partial coloring of G.

Now if we throw all the vertices in C from G, the remaining graph is bipartite because any odd cycle in G must share a vertex with C by assumption. Now we can color all of those vertices with two new colors. We have colored G with 55 colors, so χ(G)≤5