Journal of East China Normal University(Natural Sc ›› 2016, Vol. 2016 ›› Issue (1): 102-106.doi: 10.3969/j.issn.1000-5641.2016.01.005

• Article • Previous Articles     Next Articles

The chromatic number for fork-free graphs

 WANG  Xiao   

  • Received:2014-10-29 Online:2016-01-25 Published:2016-03-10

Abstract: Randerath once conjectured that every triangle-free and fork-free graph is 3-colourable. By a lemma, the conjecture for C_4-free graphs was proved.Moreover, the result that every triangle-free, C_4-free and C_{2,2,1,n}-free graph is (n+2)-colourable was proved as well, where C_{2,2,1,n} is the long handled fork with order (n+6) obtained from E-graph and P_n by joining the center vertex of E and one endvertex of P_n.

Key words: chromatic number, triangle-free;fork-free

CLC Number: