摘要
For a graph G, let be the chromatic number of G. It is well-known that holds for any graph G with clique number . For a hereditary graph class , whether there exists a function f such that holds for every has been widely studied. Moreover, the form of minimum such an f is also concerned. A result of Schiermeyer shows that every -free graph G with clique number has . Chudnovsky and Sivaraman proved that every -free with clique number graph is -colorable. In this paper, for any -free graph G with clique number , we prove that . The main methods in the proof are set partition and induction.
For a graph G, let be the chromatic number of G. It is well-known that holds for any graph G with clique number . For a hereditary graph class , whether there exists a function f such that holds for every has been widely studied. Moreover, the form of minimum such an f is also concerned. A result of Schiermeyer shows that every -free graph G with clique number has . Chudnovsky and Sivaraman proved that every -free with clique number graph is -colorable. In this paper, for any -free graph G with clique number , we prove that . The main methods in the proof are set partition and induction.
作者
Weilun Xu
Weilun Xu(School of Mathematics and Statistics, Shandong Normal University, Jinan, China)
