Graphs with \(k\) odd cycle lengths (Q1196747): Difference between revisions

Let \(L(G)\) denote the set of odd cycle lengths of a graph \(G\), i.e., \(L(G)=\{2i+1:G\) contains a cycle of length \(2i+1\}\). The relation between \(L(G)\) and the chromatic number \(\chi(G)\) is investigated in the paper. A conjecture of Gallai is verified by showing that if \(G\) is a 2-connected graph with minimum degree at least \(2k+1\) then \(| L(G)|=k\) implies \(G=K_{2k+2}\). It follows that if \(| L(G)|=k\geq 1\) then the chromatic number \(\chi(G)\) of \(G\) is at most \(2k+1\), unless some block of \(G\) is a \(K_{2k+2}\) which has the chromatic number \(2k+2\). The result verifies a conjecture of Bollobás and Erdős.