The chromatic number for fork-free graphs

WANG Xiao

(College of Mathematics and Computer Application,Shangluo University, Shangluo Shaanxi 726000,China)

The chromatic number for fork-free graphs

WANG Xiao

(College of Mathematics and Computer Application,Shangluo University, Shangluo Shaanxi 726000,China)

Randerath once conjectured that every triangle-free and fork-free graph is 3-colourable.By a lemma,the conjecture for C4-free graphs was proved.Moreover,the resu lt that every triangle-free,C4-free and C2,2,1,n-free graph is(n+2)-colourable was p roved as well,where C2,2,1,nis the long hand led fork With order(n+6)obtained from E-graph and Pnby joining the center vertex of E and one endvertex of Pn.

chromatic number;triangle-free;fork-free

0 Introduction

We consider finite,undirected and sim p le graphs G With Vertex set V(G)and edge set E(G).For a Vertex v∈V(G)and A⊆V(G),NG(v)and G［A］denote,respectively,the set of Vertices adjacent to the Vertex v and the subgraph induced by A in G.Letδ(G),Δ(G),ω(G), χ(G)denote,respectively,the minimum Vertex degree,maximum Vertex degree,clique number and chromatic number ofa graph G.The degeneracy of G,denoted by deg(G),is the maximum Value ofδ(G′)for every subgraph G′of G,that is deg(G)=m ax{δ(G′):G′⊆G}.It is well known that［1］ω(G)≤χ(G)≤deg(G)+1 holds for any graph G.

Gy′arf′as［2］introduced the concept ofχ-bound withχ-binding functions thereby extending the notion of perfectness.A family G of graphs is calledχ-bound withχ-binding function f, ifχ(G′)≤f(ω(G′))holds whenever G′is an induced subgraph of G∈G.So the family of graphs which isχ-bound With binding function f(x)=x is the family of perfect graphs.

For a giVen graph G′,a graph G is called G′-free if G contains no induced subgraph which is isomorphic to G′.Gy′arf′as［2］conjectured that if F is a forest,for any F-free graph G,there existsan integer function f(F,ω(G))such thatχ(G)≤f(F,ω(G)).And Gy′arf′as［2］proved that,where Ramsey number R(p,q)is the smallest integer m=m(p,q)such that all graphs on m Vertices contain either an independent set of cardinality p or a clique of cardinality q.Wagon［3］proved that,where 2K2denotes two independent edges.Gy′arf′as［4］proved that a k-colourable graph without triangles and rectangles(i.e.C4)contains every tree on k Vertices as an induced subgraph.More results on the chromatic number of graphs With some forbidden subgraphs,refer to［5-8］.

The H-graph(see Fig.1)is a tree With 6 Vertices which can be drawn like the capital letter H.Sim ilarly,the E-graph(see Fig.1)is the tree C2,1,2With 6 Vertices,which can be drawn like the capital letter E.The fork is the tree C2,2,1,1(see Fig.1)With 7 Vertices,which is a star With four branches With exactly two branches subdiVided once.Randerath［9］gaVe the following theorem.

Fig.1 some subgraphs

Theorem 0.1［9］Let T be a tree,such that every triangle-free and T-freegraph satisfies χ(G)≤3.Then TH or T is an induced subgraph of the fork.

And Randerath［9］proved that every triangle-free and H-free graph is 3-colourable and every triangle-free and E-free is 3-colourable.But he gaVe the following conjecture.

Con jectu re 0.2［9］Let G be a triangle-free and fork C2,2,1,1-free graph.Thenχ(G)≤3.

Fan,Xu,Ye,et al.［10］proVed that the conjecture holds for C5-free graphs.In the following section,we prove that the conjecture holds for C4-free graphs.The long hand led fork C2,2,1,n(see Fig.1)is the tree With order(n+6)obtained from E-graph and Pnby joining the center Vertex v(With dE(v)=3)of E and one end vertex of Pn,the other end Vertex of Pnis called the top of C2,2,1,n.We prove that every triangle-free,C4-free and C2,2,1,n-free graph is(n+2)-colourable.MoreoVer,we obtain that every triangle-free,C4-free and

graph is also(n+2)-colourable,whereis the tree With order(2n+4)obtained fromand Pnby joining the center Vertex ofand one endVertex of Pn.

1 Fork C2,2,1,1-free graphs

First,we start With a lemma.

Lemma 1.1 Let G be a connected triangle-free and C4-free graph.Ifχ(G)≥4 and δ(G)≥3,then there exists a fork C2,2,1,1as an induced subgraph of G.

P roo f Note thatχ(G)≥4 and triangle-freeness of G forceΔ(G)≥4(because of Brooks’Theorem)and NG(v)be an independent set in G for every v∈V(G).We take a Vertex v0such that dG(v0)≥4,there exist at least four Vertices,say v1,v2,v3,v4,in NG(v0).Sinceδ(G)≥3, we have|NG(v1){v0}|≥2 and|NG(v2){v0}|≥2.For every Vertex v∈NG(v1){v0},there exists at most one Vertex of NG(v2){v0}which is adjacent to v,otherwise there exists a C4as an induced subgraph of G.So there exist v5∈NG(v1){v0}and v6∈NG(v2){v0}such that v5v6/∈E(G).Note that C4-freeness of G forces the set{v3,v4,v5,v6}be an independent set in G.Therefore G［{v0,v1,v2,v3,v4,v5,v6}］C2,2,1,1.This completes the proof of the lemma.

Theorem 1.2 Let G bea triangle-free,C4-free and fork C2,2,1,1-freegraph.Thenχ(G)≤3.

P roof We prove the theorem for connected graphs,otherwise it suffices to prove the result for each connected component.

Suppose that Gisa connected,triangle-free,C4-free and C2,2,1,1-free graph with minimum order such thatχ(G)≥4.Then by Lemma 1.1,we haveδ(G)≤2.We take a Vertex v With dG(v)=δ(G),and let G′=G-v.It is clear that G′is also triangle-free,C4-free and C2,2,1,1-free,by minimality of G,χ(G′)≤3.Let c be a 3-colouring of G′.Since dG(v)≤2,there is a colour not appeared in the neighborhood of v,one can obtain a 3-colouring of G,a contradiction. This proVes the theorem.

2 Long hand led fork C2,2,1,n-free graphs

Lemma 2.1 Let G be a connected triangle-free and C4-free graph.Ifχ(G)≥5 and there exists a Vertex v0∈V(G)such that dG(v)≥4 for v∈V(G){v0},then there exists a C2,2,1,2as an induced subgraph of G,where v0is the top of C2,2,1,2.

This completes the proof of the lemma.

Lemma 2.2 Let G be a connected triangle-free and C4-free graph,n≥2 be an integer. Ifχ(G)≥n+3 and there exists a Vertex v0∈V(G)such that dG(v)≥n+2 for any v∈V(G){v0},then there exists a C2,2,1,n′as its induced subgraph,where n′≥n and v0is the top of C2,2,1,n′.

P roof The proof is made by induction on n.If n=2,by Lemma 2.1,the result holds. Assume that let G be a connected triangle-free and C4-free graph which satisfiesχ(G)≥n+3 and there exists a Vertex v0such that dG(v)≥n+2 for any v∈V(G){v0},the result is true. Now,we w ill prove that ifχ(G)≥n+4 and there exists a Vertex v0such that dG(v)≥n+3 for any v∈V(G){v0},then G contains a C2,2,1,n′as its induced subgraph,where n′≥n+1 and v0is the top of C2,2,1,n′.

Let M(v0)=V(G)({v0}∪NG(v0)),the Vertex set V(G)can be partitioned into{v0}, NG(v0)and M(v0).We have the following two facts.

Fact 1 deg(G［M(v0)］)≥n+2.

Otherw ise,suppose deg(G［M(v0)］)≤n+1,and thusχ(G［M(v0)］)≤n+2.Let c be a(n+2)-colouring of G［M(v0)］.Note that the triangle-freeness of G forces NG(v0)be an independent set.Then by assigning a new colour to the Vertices in NG(v0)and a colour used by c to v0,we obtain a(n+3)-colouring of G,which contradictsχ(G)≥n+4.

By Fact 1,we can let A be a subset of M(v0)With maximum cardinality such that δ(G［A］)≥n+2.

Fact 2χ(G［A］)≥n+3.

Otherwise,supposeχ(G［A］)≤n+2,let B=M(v0)A,because ofχ(G)≥n+4, then B/=ø.Let k be the maximum integer such that for any B′⊆B With cardinality k, χ(G［A∪B′］)≤n+2.By the maximality of A,it is clear that k≥1.Let B0be a subset of B with|B0|=k+1 andχ(G［A∪B0］)≥n+3.On the other hand,by the choice of A, δ(G［A∪B0］)≤n+1,and thus there exists a Vertex,say v′,in B0,With dG［A∪B0］(v′)≤n+1. And by the assumptionχ(G［A∪B0{v′}］)≤n+2,it follows thatχ(G［A∪B0］)≤n+2,a contradiction.

Since G is connected,we can choose a shortest path P from v0to A.Note that N(v0)∩M(v0)=øand A⊆M(v0),so NG(v0)∩A=ø.Let P=v0v1···vι(l≥2),where l is the length of P,vι∈A and vi/∈A for each i=1,2,···,l-1.By Fact 2,app ly induction to G［A∪{vι-1}］, there exists an induced subgraph G′of G［A∪{vι-1}］,which is isomorphic to C2,2,1,n′With n′≥n and vι-1is the top of C2,2,1,n′.Thus,G［V(G′)∪V(P)］is an induced subgraph,which is isomorphic to C2,2,1,n′′,with n′′≥n′+1≥n+1 and v0is the top of C2,2,1,n′′.This proVes the lemma.

By Lemma 1.1,2.2,the following Lemma is obtained triVially.

Lemma 2.3 Let G be a connected triangle-free and C4-free graph,n be a positiVe integer.Ifχ(G)≥n+3 andδ(G)≥n+2,then there exists a C2,2,1,nas an induced subgraph of G.

Theorem 2.4 Let G be a triangle-free,C4-free and C2,2,1,n-free graph,n be a positiVe integer.Thenχ(G)≤n+2.

Proof We prove the result for each connected com ponent of G by contradiction.W ithout loss of generality,suppose G is a connected,triangle-free,C4-free and C2,2,1,n-free graph With minimum order such thatχ(G)≥n+3.Then by Lemma 2.3,δ(G)≤n+1.We take a Vertex v With dG(v)=δ(G),and let G′=G-v.It is clear that G′is also triangle-free,C4-free and C2,2,1,n-free,and by the minimality of G,χ(G′)≤n+2.Let c be a(n+2)-colouring of G′. Since dG(v)≤n+1,there is a colour not appeared in the neighborhoods of v,by assigning it to v,one can obtain a(n+2)-colouring of G,a contradiction.This proVes the theorem.

Byδ(G)≥n+2,triangle-freeness and C4-freeness of G,one can obtain the following lemma from Lemma 2.3.

Lemma 2.5 Let G be a connected triangle-free and C4-free graph,n≥2 be an integer. Ifχ(G)≥n+3 andδ(G)≥n+2,then there exists a

as induced subgraph of G.

Similarly to the proof of Theorem 2.4,by Lemma 2.5 and the result［8-9］eVery triangle-free and E-free is3-colourable,wehaVe the following stronger theorem.(Note thatE for n=1.)

Theorem 2.6 Let G be a triangle-free,C4-free and-free graph,n be a positiVe integer.Thenχ(G)≤n+2.

［1］REINHARD D.Graph Theorey(Second Edition)［M］.Hong K ong:Sp ringer-Verlag,2000:95-117.

［2］GY＇ARF＇AS A.problems from the world surrounding perfect graphs［J］.Zastow M at,1987,19:413-441.

［3］WAGON S.A bound on the chromatic number of graphs without certain induced subgraphs［J］.J of Com bin Theory,Series B,1980,29(3):345-346.

［4］GY＇ARF＇AS A,SZEM ER＇ED I E and Tuza.Induced sub trees in graphs 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{2K1+K2,C4}-free graphs［J］.Journal of East China Norm a l 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.

(责任编辑李艺)

不含叉形图为导出子图的图的色数

王晓
(商洛学院数学与计算机应用学院,陕西商洛726000)

Randerath曾猜想每一个不含三角形和不含叉形图为导出子图的图是3-可着色的.通过一个引理,证明了该猜想在没有长为4的圈的图类上是成立的.进而,还证明了每一个不含三角形、不含C4并且不含C2,2,1,n作为导出子图的图是(n+2)-可着色的,这里C2,2,1,n表示将图E的中心点和路Pn的一个端点连接而得到的阶为(n+6)的长把叉形图.

色数;不含三角形;不含叉形图

2014-10

陕西省教育厅自然科学专项基金(12JK 089);商洛学院科研基金(12SKY 011)

王晓,男,硕士,讲师,研究方向为图论及其应用.E-mail:wangxiaomath@163.com.

O175.5 Document code:A

10.3969/j.issn.1000-5641.2016.01.013

1000-5641(2016)01-0102-05