On the chromatic number of graphs of odd girth without longer odd holes

摘要

An odd hole is an induced odd cycle of length at least five. Let l >= 2 be an integer, and let gl denote the family of graphs which have girth 2l + 1 and have no holes of odd length at least 2l + 3. Chudnovsky and Seymour proved that every graph in g2 is three-colorable. Following the idea of Chudnovsky and Seymour, Wu, Xu and Xu proved graph G is an element of & Union; that every graph in g3 is three-colorable. In 2022, Wu, Xu and Xu conjectured that every l >= 2 gl is three-colorable. In this paper, we prove that every graph G is an element of gl with radius at most l + 3 is three-colorable.

关键词