Journal of East China Normal University(Natural Science) >

2016 , Vol. 2016 >Issue 1: 102 - 106

DOI: https://doi.org/10.3969/j.issn.1000-5641.2016.01.005

Article

The chromatic number for fork-free graphs

  • WANG Xiao
Expand

Received date: 2014-10-29

  Online published: 2016-03-10

Fold

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

Cite this article

WANG Xiao . The chromatic number for fork-free graphs[J]. Journal of East China Normal University(Natural Science), 2016 , 2016(1) : 102 -106 . DOI: 10.3969/j.issn.1000-5641.2016.01.005

References

[1]REINHARD D. Graph Theorey (Second Edition) [M]. Hong Kong:Springer-Verlag, 2000: 95-117.
[2]GY\'{A]RF\'{A]S A. Problems from the world surrounding perfect graphs [J]. Zastow Mat, 1987, 19: 413-441.
[3]WAGON S. A bound on the chromatic number of graphs without certain induced subgraphs [J]. J of Combin Theory, Series B, 1980, 29(3):345-346.
[4]GY\'{A]RF\'{A]S A, SZEMER\'{E]DI E and Tuza. Induced subtrees ingraphs of large chromatic number [J]. Discrete Math, 1980, 30(3):235-244.
[5] DUAN F and WU B Y. On chromatic number of graphs without certain induced subgraph [J]. Ars combinatoria, 2011, 101: 33-34.
[6] DUAN F and ZHANG W J. On chromatic number of $\{2K_1+K_2, C_4\]$-free graphs [J]. Journal of East China Normal University: Natural Science, 2014(1): 9-12.
[7] RANDERATH B, SCHIERMEYER I.  A note on Brooks' theorem for triangle-free graphs [J]. Australas J Comb, 2002, 26: 3-9.
[8] RANDERATH B, SCHIERMEYER I. Vertex coloring and forbidden subgraphs-a survey [J]. Graphs Combin, 2004, 20(1): 1-40.
[9] RANDERATH B. The Vizing bound for the chromatic number based on forbidden pairs [D]. Nordrhein-Westfalen: RWTH Aachen University, 1998.
[10] FAN G, XU B, YE T, et al. Forbidden subgraphs and 3-colorings [J]. Siam J Disc Math, 2014, 28: 1226-1256.
Options
Outlines

/

〈 〉