Graphs with k odd cycle lengths

✍ Scribed by A. Gyárfás

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 481 KB
• Volume: 103
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90037-g

✦ Synopsis

Gyarf&, A., Graphs with k odd cycle lengths, Discrete Mathematics 103 (1992) 41-48.

If G is a graph with k z 1 odd cycle lengths then each block of G is either KZk+2 or contains a vertex of degree at most 2k. As a consequence, the chromatic number of G is at most 2k + 2. For a graph G let L(G) denote the set of odd cycle lengths of G, i.e., L(G) = (2i + 1: G contains a cycle of length 2i + l}. With this notation, bipartite graphs are the graphs with IL(G)1 = 0. Bollobas and Erd& asked how large can the chromatic number of G be if ]L(G)] = k. They conjectured that (L(G)1 = k implies x(G) < 2k + 2 and this is best possible considering G = Kzk+*.

The case k = 1 is checked by Bollobas and Shelah (see [l, p. 4721 for the motivation). Gallai suspected that a stronger statement is true, namely if G is 2-connected, IL(G)1 = k, G # Kzk+* then the minimum degree of G is at most 2k. The aim of this paper is to prove this stronger version of the original conjecture.

Theorem 1. Zf G is a 2-connected graph with minimum degree at least 2k + 1 then (L(G)1 = k 2 1 implies G = K2k+2.

Assuming that JL(G)( = k, Theorem 1 clearly allows to color the vertices of the blocks of G with at most 2k + 1 colors except when a block is a K,,,,. Thus the following corollary is obtained.

Corollary. Zf (L(G)1 = k 3 1 then the chromatic number of G is at most 2k + 1, unless some block of G is a K,,,,.

(Zf there is such a block, then the chromatic number of G is 2k + 2.)