Graphs with Odd Cycle Lengths 5 and 7 are 3-Colorable
Tomáš Kaiser, Ondřej Rucký, Riste Škrekovski · SIAM Journal on Discrete Mathematics · 2011
Let [Formula: see text] denote the set of all odd cycle lengths of a graph [Formula: see text]. Gyárfás gave an upper bound for [Formula: see text] depending on the size of this set: if [Formula: see text], then [Formula: see text] unless some block of [Formula: see text] is a [Formula: see text], in which case [Formula: see text]. This bound is generally tight, but when investigating [Formula: see text] of special forms, better results can be obtained. Wang completely analyzed the case [Formula: see text]; Camacho proved that if [Formula: see text], [Formula: see text], then [Formula: see text]. We show that [Formula: see text] implies [Formula: see text].