# Theχ-Boundedness of P2∪P3-Free Graphs

Authors: Xiao Wang; Donghan Zhang
Journal: Journal of Mathematics
 (2022)

---

## Abstract

In the early 1980s, Gyárfás introduced the concept of theχ-bound with χ-binding functions thereby extending the notion of perfectness. There are a number of challenging conjectures about the χ-bound. Let χG, ωG, and ΔG be the chromatic number, clique number, and maximum degree of a graph G, respectively. In this paper, we prove that if G is a triangle-free and P2∪P3-free graph, then χG≤3 unless G is one of eight graphs with ΔG=5 and χG=4, where the eight graphs are extended from the Grötzsch graph as a Mycielskian of a 5-cycle graph. Moreover, we also show that χG≤3ωG if G is a P2∪P3,W4-free graph.


---

## Body

## 1. Introduction

We consider finite graphs only and refer to [1] for undefined terminology and notation. Let G be a graph. A k-colouring of G is an assignment of k colours to its vertices such that no adjacent vertices are assigned the same colour. The minimum k for which G has a k-colouring is called its chromatic number and denoted χG. For a subset Q⊆VG, we call Q a clique of G if all two vertices of Q are adjacent in G. The cardinality of a maximum clique of G is called its clique number and denoted ωG.Letℋ be a family of graphs. A graph G is called ℋ-free if G does not contain an induced copy of any H∈ℋ. In particular, we simply write H-free instead of H-free if ℋ=H. A family G of graphs is called χ-bound with χ-binding function f if χH≤fωH holds whenever H is an induced subgraph of G∈G, which is initiated by Gyárfás [2] and extended the notion of perfectness. Gyárfás [2] conjectured that for each forest F, there exists an integer function fF,x such that χG≤fF,ωG where G is a F-free graph.LetG1 and G2 be disjoint graphs, their union graphG1∪G2 is the graph with VG1∪G2=VG1∪VG2 and EG1∪G2=EG1∪EG2. The union graph G∪G is simply denoted by 2G. Wagon [3] proved that f2P2,ωG≤1/2ωGωG+1. Randerath and Schiermeyer [4] established that fP4∪K1,ωG≤1/2ωGωG+1. For more results on the chromatic number of graphs with some forbidden subgraphs, we refer to [5–9].The graphP2∪P3 is the union graph of paths P2 and P3. Recently, Bharathi and Choudum [10] have shown that fP2∪P3,ωG≤1/6ωGωG+1ωG+2 and obtained the sharper bounds for P2∪P3,diamond-free graphs. Here, we give the following result for triangle-free and P2∪P3-free graphs.Theorem 1.
LetG be a triangle-free and P2∪P3-free graph. Then, χG≤3 unless G is the one of eight graphs with ΔG=5 and χG=4, as shown in Figure 1, where the eight graphs are extended from the Grötzsch graph as a Mycielskian of a 5-cycle graph.In paper [11], Choudum and Karthick gave the χ-bounding for P2∪P3,C4-free graphs.Figure 1
Eight graphs withΔ=5 and χ=4.Theorem 2 (Choudum and Karthick [11]).
LetG be a P2∪P3,C4-free graph. Then, χG≤5ωG/4.LetWn be a wheel with an order n+1, which is obtained from the star K1,n by connecting all leaves in a circuit Cn. In this paper, we study the χ-bounding for P2∪P3,W4-free graphs and obtain the following result.Theorem 3.
LetG be a P2∪P3,W4-free graph. Then, χG≤3ωG.


## 2. Proof of Theorem 1

LetG=VG,EG be a graph. For a vertex subset U⊂VG, the neighborhoodNGU of U is defined to be the set(1)v∈VG∖U:there existsu∈Usuch thatuv∈EG.The closed neighborhoodNGU of U is NGU∪U, and the induced subgraph GU of U is the subgraph of G whose vertex set is U and whose edge set consists of all edges of G which have both ends in U. If there is no confusion, NGU, NGU, and GU are simply denoted by NU, NU, and U, respectively.We need the following lemma to prove Theorem1.Lemma 1.
LetG be a triangle-free and P2∪P3-free graph. Then, χG≤4.Proof.
The result is trivial forEG=∅. Let xy∈EG and M=VG\Nx∪Ny, where Nx and Ny are the neighborhood of x and y, respectively. The triangle-freeness implies that Nx and Ny are disjoint independent sets. The P2∪P3-freeness implies that M is a disjoint union of complete graphs. Since M is triangle-free, we have that M is a disjoint union of independent vertices and independent edges. Therefore,(2)χG≤χNx∪Ny+χM≤2+2=4.
A connected graphG is called a near-bipartite graph if there exists a vertex v∈VG such that Nv is a star and VG\Nv is a bipartite graph where Nv is the closed neighborhood of v in G. Clearly, χG≤3 for every near-bipartite graph G.Proof of Theorem 1.
Without loss of generality, suppose thatG is connected. Let ΔG be the maximal degree of G and x0 be a vertex of G such that dx0=ΔG. The triangle-freeness implies that Nx0 is a star.
LetM=VG\Nx0. If M is C5-free, it follows from P2∪P3,triangle-freeness that M is a bipartite graph. Since Nx0 is a star, G is near-bipartite. Thus, χG≤3. Suppose that M has a C5 as it is an induced subgraph. Let(3)Nx0=v0,v1,…,vΔG−1,C5=u0u1u2u3u4u0,H=Nx0∪VC5.
TheP2∪P3-freeness implies that there exist at least two vertices of VC5 which are adjacent to vk, and the triangle-freeness implies that there exist at most two nonadjacent vertices of VC5 which are adjacent to vk, where k∈0,1,…,ΔG−1. So(4)Nvk∩VC5=ui,ui+2,where each indic ofuare taken modulo5.
If there existk,l∈0,1,…,ΔG−1 such that NHvk=NHvl, without loss of generality, say u0vk,u2vk,u0vl,u2vl∈EG by (4), then u3,u4,vk,x0,vl≅P2∪P3, a contradiction. Thus,(5)Nvk∩Nvl∩VC5≤1,for0≤k<l≤ΔG−1.
By (4) again,(6)2×ΔG+10≤∑i=04dGui≤5ΔG.
Then,ΔG≥4, and we have the following three cases to prove Theorem 1.Case 1.
ΔG=4 In this case, Nx0=v0,v1,v2,v3. By (4) and (5), we have that(7)1≤Nui∩v0,v1,v2,v3≤2,fori=0,1,2,3,4.
By (4), (5), and (7), it is checked that H≅G1′, as shown in Figure 2. Without loss of generality, let H=G1′.
If there exists a vertexw∈VG\VH such that vkw∈EG and w∉NVC5, then u3,u4,x0,vk,w≅P2∪P3, a contradiction. Thus,(8)Nvk⊆NVC5∪x0for0≤k≤3.
SinceΔG=4, it follows from (8) that there are possible three cases: (i) du1=du3=3, (ii) du1,du3=3,4, and (iii) du1=du3=4 by extending from H (=G1′ as shown in Figure 2) to G.For (i),G=H=G1′, as shown in Figure 2For (ii), without loss of generality, suppose thatdu1=4 and du3=3. Let w∈VG\VH be the neighbour of u1. Since du3=3, wu3∉EG. The triangle-freeness forces that wv2∉EG. Then,(9)wv0∉EGor elseu3,u4,v0,w,u1≅P2∪P3,wv1∈EGor elseu1,w,x0,v1,u3≅P2∪P3,wv3∈EGor elseu1,w,x0,v3,u4,≅P2∪P3.If there existsw′∈VG\VH∪w, then w′,VH=∅ since du3=3 and (8). Thus, ww′∈EG. And, then w,w′,u2,u3,u4≅P2∪P3, a contradiction. So, G≅G2′, as shown in Figure 2.For (iii), ifu1,u3 have the same neighbour in VG∖VH, say w, then P2∪P3-freeness implies that wv0,wv3∈EG. By (8) and ΔG=4, G≅G3′, as shown in Figure 2. Otherwise, u1,u3 have different neighbours in VG∖VH, say w1,w2, respectively. The P2∪P3-freeness implies that v1w1,v3w1,v0w2,v2w2∈EG. Thus, w1w2∈EG or else v1,w1,v0,w2,v2≅P2∪P3. Therefore, VH∪w1,w2 is a 4-regular graph. That is, G≅G4′, as shown in Figure 2.
Now, it is sufficient to prove that each member of Figure2 has a 3-colouring. Since Gi′NGi′u0 is a star and Gi′VGi′\NGi′u0 is a bipartite graph, Gi′ is near-bipartite for i=1,2,3. And, then they have a 3-colouring. For the graph G4′ of Figure 2, we check that χG4′=3 directly, see Figure 2.Figure 2
Four graphs withΔ=4.Case 2.
ΔG=5. In this case, Nx0=v0,v1,v2,v3,v4. We claim that G is isomorphic to one member of Figure 1.
Suppose there existsui∈VC such that dHui=ΔG=5. Without loss of generality, let uiv0,uiv1,uiv2∈EH. By (4), Nv0∪Nv1∪Nv2∩VC5⊆ui,ui−2,ui+2 where each indices of u are taken modulo 5. On the other hand, by (4) and (5),(10)Nv0∪Nv1∪Nv2∩VC5=Nv0∩VC5∪Nv1∩VC5∪Nv2∩VC5=∑k=02Nvk∩VC5−∑0≤i<j≤2Nvi∩Nvj∩VC5+Nv0∩Nv1∩Nv2∩VC5≥6−3+1=4.
A contradiction. Therefore,dHui≤4 for 0≤i≤4. It follows from (4) that ∑i=04dHui≥10+2×ΔG=20. Thus,(11)dHui=4,for0≤i≤4.
By (4), (5), and (11), it is checked that H≅G1, as shown in Figure 1 (G1 is the Grötzsch graph as a Mycielskian of a 5-cycle graph). Without loss of generality, suppose that H=G1.
By a similar argument in (8) of Case 1, we obtain that(12)Nvk⊆NVC5∪x0,for0≤k≤4.
Suppose that there existsw∈VG\VH such that wu0∈EG. The triangle-freeness implies wuk,wvk∉EG with k=1,4. If wu3∈EG, then the triangle-freeness forces wu3∉EG and wvk∈EG for k=0,2 or else x0,vk,u0,w,u2≅P2∪P3. Thus, u3,v4,w,v0,u1≅P2∪P3, a contradiction so wu3∉EG and wu2∉EG by the same argument. And we have that(13)wvk∈EGfork=2,3or elseu0,w,u2,u3,vk,≅P2∪P3,wv0∉EGor elsev0,w,u3,u2,v1≅P2∪P3.
Fori=1,2,3,4, by the same argument, we obtain that(14)If there existswi∈VG\VHsuch thatwiui∈EG,thenwivi+2,wivi+3∈EGandNwi∩VHui,vi+2,vi+3=∅,where the indices are taken modulo5.
LetW=w∈VG\VH:w∈NC5. By (14), W≤5. If there exists y∈VG\VH∪NC5, then Ny∩VH=∅ by (12). That is, there exists w∈W such that yw∈EG. Thus, y,w,v0,x0,v1≅P2∪P3, a contradiction. Therefore,(15)W≤5andVG=VH∪W.
If there existwi,wi+2∈W such that wiui,wi+2ui+2∈EG, then wiwi+2∈EG (or else wi,ui,vi,wi+2,vi+3≅P2∪P3 by (14), and if there exist wi,wi+1∈W such that wiui,wi+1ui+1∈EG, then wiwi+1∉EG or else wi,wi+1,ui+2,ui+3,ui+4≅P2∪P3 by (14), where the indices are taken modulo 5. By (14) and (15) again, as shown in Figure 1, we have that(16)G≅G1,ifW=0,G2,ifW=1,G3orG4,ifW=2,G5orG6,ifW=3,G7,ifW=4,G8,ifW=5.
It is well known that the Grötzsch graph as a Mycielskian of a 5-cycle graph (seeG1 in Figure 1) satisfies one’s chromatic number is 4. By Lemma 1, χG=4 where G is one member of Figure 1.Case 3.
ΔG≥6. Suppose that dHu0≥5, without loss of generality, let v0,v1,v2⊂Nu0∩Nx0. The triangle-freeness forces that Nuk∩v0,v1,v2=∅ for k=1,4. And then the P2∪P3-freeness forces that there exist at least two vertices of v0,v1,v2 which are adjacent to u2, say u2v0,u2v1∈EG. Thus, u3v0,u3v1∉EG since G is triangle-free. So, u3,u4,v0,x0,v1≅P2∪P3, a contradiction. Therefore, dHu0≤4, and dHu1≤4 similarly. Thus,(17)Nu0∪Nu1∩Nx0=NHu0∪NHu1∩Nx0≤NHu0∩Nx0+NHu1∩Nx0≤4−2+4−2=4.
SinceNx0=ΔG≥6, there exist two vertices in Nx0, say v′ and v″, which are adjacent to neither u0 nor u1. Then, u0,u1,v′,x0,v″≅P2∪P3, a contradiction.
This completes Proof of Theorem 1.


## 3. Proof of Theorem3

LetA and B be disjoint subsets of VG. The set of all edges in G with one end in A and another end in B is denoted by A,B, and if every vertex in A is adjacent to every vertex in B, then A,B is said to be complete. We call A an independent set of G if no two vertices of A are adjacent in G. For the sake of convenience, if H is an induced subgraph of G, we write H⊑G.Proof of Theorem 3.
IfG is C4-free, by Theorem 2, then χG≤5ω/4<3ωG. So we suppose that G contains a C4 as it is an induced subgraph, let C4=v0v1v2v3v0, N0=VC4, and(18)A=x∈VG\N0:Nx∩N0=1,B=x∈VG\N0:Nx∩N0=2,C=x∈VG\N0:Nx∩N0=3,M=x∈VG\N0:Nx∩N0=0.
Then, it is easily verified thatVG=N0∪A∪B∪C∪M. For convenience, we further partition A,B, and C as follows:(19)Ai=x∈VG\N0:Nx∩N0=vi,Bi=x∈VG\N0:Nx∩N0=vi,vi+1,Bi′=x∈VG\N0:Nx∩N0=vi,vi+2,Ci=x∈VG\N0:Nx∩N0=vi−1,vi,vi+1.
Then,A=∪i=03Ai, B=∪i=03Bi∪B0′∪B1′, and C=∪i=03Ci. Unless otherwise stated, we assume that the indices are taken modulo 4 in this section. For each i∈0,1,2,3, we have the following results.R 3.1. M is an independent set (or else P2∪P3⊑G).R 3.2. Ai is an independent set (or else P2∪P3⊑G).R 3.3. Bi is the disjoint union of complete graphs (or else P2∪P3⊑G).R 3.4. Bi′ is the disjoint union of complete graphs (or else W4⊑G).R 3.5. Ci is complete (or else W4⊑G).R 3.6. M,Ai=∅ (or else P2∪P3⊑G).R 3.7. Ci,Ci+2=Ci,Bi+1′=∅ (or else W4⊑G).By R 3.3, letmi is the number of components of Bi, then Bi=Q1i∪Q2i∪…∪Qmii where Qli is complete and Qli,Qji=∅ with 1≤l≠j≤mi.R 3.8. If Bi≠∅, then mi−1≤2 and mi+1≤2.Proof of R 3.8. Suppose that mi+1≥3, there exist y1∈Q1i+1, y2∈Q2i+1, and y3∈Q3i+1 such that y1,y2,y3 is an independent set. Let x∈Bi, the P2∪P3-freeness forces that Nx∩y1,y2,y3≥2, say xy1,xy2∈EG. Thus, x,y1,vi+2,y2,vi+1≅W4, a contradiction. So mi+1≤2. By the similar argument, one get mi−1≤2.R 3.9. If mi=mi+1=2, then Bi and Bi+1 are both independent sets with order two, and Bi∪Bi+1≅2P2.Proof of R 3.9. Since mi=mi+1=2, let Bi=Q1i∪Q2i, Bi+1=Q1i+1∪Q2i+1, and x1∈Q1i,x2∈Q2i, y1∈Q1i+1,y2∈Q2i+1. The P2∪P3-freeness forces that Nx1∩y1,y2≠∅ and Nx2∩y1,y2≠∅. The W4-freeness forces that Nx1∩y1,y2≤1 and Nx2∩y1,y2≤1. So Nx1∩y1,y2=Nx2∩y1,y2=1. Without loss of generality, let x1y1∈EG, then x2y1∉EG or else vi,x1,y1,x2,vi+1≅W4. Therefore, x2y2∈EG. Thus, x1,x2,y1,y2≅2P2.Suppose there existsx1′≠x1∈Q1i, then x1′y2∉EG or else vi,x2,y2,x2,vi+1≅W4. And then, x1,x1′,x2,y2,vi+2≅P2∪P3, a contradiction. So Q1i=1. By the similar argument, Q2i=Q1i+1=Q2i+1=1. Therefore, Bi=Bi+1=2 and Bi∪Bi+1≅2P2.R 3.10. If mi=mi+1=1, then Bi∪Bi+1≅Kt or Kt−e.Proof of R 3.10. Since mi=mi+1=1, Bi and Bi+1 are complete. Suppose that there exist x∈Bi, y∈Bi+1 such that xy∉EG, it suffices to show that x,Bi+1\y and Bi\x,Bi+1 are both complete. If there exists y′∈Bi+1\y such that xy′∉EG, then y,y′,x,vi,vi−1≅P2∪P3, a contradiction. So x,Bi+1\y is complete. Let x′∈Bi\x, y′∈Bi+1 such that x′y′∉EG. If y′=y, then x,x′,y,vi+2,vi+3≅P2∪P3, a contradiction. Otherwise, y′≠y, the P2∪P3-freeness forces that xy′,x′y∈EG, and thus, x,x′,y′,y,vi+1≅W4, a contradiction. So Bi\x,Bi+1 is complete.R 3.11. If Bi≠∅ for each i∈0,1,2,3, then mj:mj=2,0≤j≤3≤1.Proof of R 3.11. By R 3.8, we have mj≤2 for each j∈0,1,2,3. Suppose mj:mj=2,0≤j≤3≥2, without loss of generality, let m0=m1=2 or m0=m2=2.Ifm0=m1=2, by R 3.9, let x1,x2∈B0, y1,y2∈B1, x1x2,y1y2∉EG and x1,x2,y1,y2≅2P2, say x1y1,x2y2∈EG. Let z∈B2, then W4-freeness forces y1,y2⊈Nz and the P2∪P3-freeness forces y1,y2∩Nz≠∅. Without loss of generality, let y1z∈EG and y2z∉EG. The P2∪P3-freeness and x1y2∉EG force x1z∈EG. Thus, v1,v2,x1,y1,z≅W4, a contradiction.Now, suppose thatm0=m2=2. Let x1,x2∈B0,z1,z2∈B2,y∈B1, and x1x2,z1z2∉EG. The P2∪P3,W4-freeness forces that x1,x2∩Ny=1 and z1,z2∩Ny=1, say x1y,z1y∈EG and x2y,z2y∉EG. Thus,(20)x1z1∉EGor elsev1,v2,x1,z1,y≅W4,x1z2∈EGor elsev1,x1,z1,v3,z2≅P2∪P3,x2z1∈EGor elsev2,z1,x1,v0,x2≅P2∪P3,x2z2∈EGor elsev0,x2,y,v2,z2≅P2∪P3.Letw∈B3. The P2∪P3,W4-freeness forces that x1,x2∩Nw=z1,z2∩Nw=1. If wx1∈EG, then wy∉EG (or else v0,v1,y,w,x1≅W4) and wx2∉EG. And then w,v3,y,v1,x2≅P2∪P3, a contradiction. So, wx1∉EG, and wz1∉EG similarly. Thus, v2,z1,x1,v0,w≅P2∪P3, a contradiction.R 3.12. If Bi≠∅ for each i∈0,1,2,3 and mj|mj=2,0≤j≤3=1, then B0∪B1∪B2∪B3≅C5.Proof of R 3.12. Without loss of generality, let m0=2, m1=m2=m3=1, and B0=Q10∪Q20. By R 3.3, Q10 and Q20 are both complete. Suppose that Q10≥2 and Q20≥2. Let x1,x2∈Q10, x1′,x2′∈Q20, and y∈B1. The P2∪P3-freeness forces y,x1,x2,x1′,x2′≠∅, say x1y∈EG. Then, y,x1′,x2′≠∅ (or else x1′,x2′,x1,y,v2≅P2∪P3), say x1′y∈EG. And thus, x1,v0,x1′,y,v1≅W4, a contradiction. So, there is at least one with order 1 of Q10,Q20.LetB0=Q10∪x0, and x1∈Q10, y∈B1,z∈B2,w∈B3. The P2∪P3,W4-freeness forces Ny∩x1,x0=Nw∩x1,x0=1. Suppose that Ny∩x1,x0=Nw∩x1,x0, without loss of generality, let x1y,x1w∈EG. Then, yw∈EG or else y,v2,x0,v0,w≅P2∪P3. And thus, v0,v1,y,w,x1≅W4, a contradiction. So Ny∩x1,x0≠Nw∩x1,x0, without loss of generality, let x1y,x0w∈EG and x0y,x1w∉EG. Then, yw∈EG or else w,x0,x1,y,v2≅P2∪P3.TheP2∪P3-freeness forces Nz∩x1,x0≥1. Without loss of generality, let x1z∈EG, then zy∉EG or else x1,v1,v2,z,y≅W4. And then, x0z∈EG or else v3,z,x0,v1,y≅P2∪P3. And wz∉EG or else x0,v0,v3,z,w≅W4. Therefore, x0,x1,y,z,w≅C5.Next, it suffices to show thatQ10=B1=B2=B3=1.If there existsx1′≠x1∈Q10, then the P2∪P3-freeness forces x1′y∈EG and x1′w∈EG. Thus, v0,v1,y,w,x1′≅W4, a contradiction. So Q10=1.If there existsy′≠y∈B1, then yy′∈EG since m1=1. The P2∪P3-freeness forces x0y′∈EG and zy′∈EG. Thus, x0,v1,v2,z,y′≅W4, a contradiction. So B1=1, and B3=1 similarly.If there existsz′≠z∈B2, then zz′∈EG since m2=1. The P2∪P3-freeness forces yz′∈EG and wz′∈EG. Thus, w,y,v2,v3,z′≅W4, a contradiction. So B2=1.R 3.13. If there exist x∈B0, y∈B1, z∈B2, w∈B3 such that C4=xyzwz is an induced subgraph, then A=∅.Proof of R 3.13. Without loss of generality, let A0≠∅ and a∈A0. If ax∈EG, then az∈EG (or else v3,z,v1,x,a≅P2∪P3), and aw∈EG (or else v2,y,a,v0,w≅P2∪P3). Thus, v0,v3,z,a,w≅W4, a contradiction. So ax∉EG. And then az∈EG or else v2,z,x,v0,a≅P2∪P3. Thus, v1,x,v3,z,a≅P2∪P3, a contradiction.R 3.14. If there exist x,x′∈Bi, y∈Bi+1, z∈Bi+2, w∈Bi+3 such that C5=xx′yzwx is an induced subgraph, then A=∅.Proof of R 3.14. By the symmetry, it is sufficient to prove that Ai=Ai+2=∅.Suppose thatAi≠∅, and a∈Ai. If ax∉EG, then the P2∪P3-freeness implies that ay∈EG and az∈EG. And then, aw∈EG or else vi+3,w,a,y,vi+1≅P2∪P3. Thus, vi,a,z,vi+3,w≅W4, a contradiction. So ax∈EG. And ax′∈EG or else vi+2,vi+3,a,x,x′≅P2∪P3. Thus, aw∈EG (or else vi+3,w,a,x′,vi+1≅P2∪P3), and az∈EG (or else vi+3,z,a,x′,vi+1≅P2∪P3). And then vi,a,z,vi+3,w≅W4. There is also a contradiction.Suppose thatAi+2≠∅ and b∈Ai+2. The P2∪P3-freeness forces that x′b∈EG and wb∈EG. It follows from W4-freeness that yb∉EG and zb∉EG. And bx∈EG or else vi,x,b,vi+2,z≅P2∪P3. Thus, vi,x′,b,w,x≅W4, a contradiction.R 3.15. If there exists i∈0,1,2,3 such that Bi≤1, then χG≤25ωG−1/4+1.Proof of R 3.15. Without loss of generality, suppose that B0≤1. Let(21)S1=A2∪B1∪B2∪B2′∪C1∪C2∪C3∪v1,v3,S2=A3∪B3∪B1′∪C0∪v2,v0,S3=A1∪A0∪M.Then,S1=Nv2, S2⊆Nv3 and VG=S1∪S2∪S3∪B0. It follows from W4-freeness that S1 and S2 are both C4-free. By Theorem 2,(22)χS1≤5ωS14≤5ωG−14,χS2≤5ωS24≤5ωG−14.By R 3.1, R 3.2 and R 3.6,χS3≤2. Thus,(23)χG≤∑k=13χSk+χB0≤25ωG−14+2+1=25ωG−14+1.LetG be a graph on n vertices v1,v2,…,vn and H1,H2,…,Hn be pairwise disjoint graphs. An expansion of G, denoted by GH1,H2,…,Hn, is the graph obtained from G by replacing the vertex vi of G by Hi, i=1,2,…,n and joining the vertices x∈Hi, y∈Hj if and only if vivj∈EG. If His are complete, it is called a complete expansion of G and is denoted by KGk1,k2,…,kn where Hi=Kki. The graph KC4k1,k2,k3,k4 is denoted by KC4 simply. Clearly, KC4 is the complement of a bipartite graph. Thus, KC4 is a perfect graph so does KC4−e.R 3.16. If Bi≥2 for each i∈0,1,2,3 and m0=m1=m2=m3=1, then there exists T⊂R such that R\T≅KC4 (or KC4−e) where R=B0∪B1∪B2∪B3 and χT≤2.Proof of R 3.16. Since m0=m1=m2=m3=1, each Bii∈0,1,2,3 is complete. Let Ri=Bi∪Bi+1, then Ri≅Kt (or Kt−e) for each i∈0,1,2,3 by R 3.10, where t=VRi. Let p=Ri:Ri≅KVRi−e,0≤i≤3.Ifp≤1, it follows from the W4-freeness that B0,B2=B1,B3=∅. Thus, R≅KC4 (or KC4−e).Ifp=2, then there exist x∈Bi,y∈Bi+1 such that xy∉EG for some i∈0,1,2,3. Since Bi≥2, Bi∖x≠∅. The W4-freeness forces that Bi∖x,Bi+2=Bi+1,Bi+3=∅. Let T=x, then R\T≅KC4 (or KC4−e) and χT=1.Ifp=3, then there exist x∈Bi,y∈Bi+1,z∈Bi+2,w∈Bi+3 such that xy∉EG and zw∉EG for some i∈0,1,2,3. Since Bi∖x≠∅ and Bi+2∖z≠∅, the W4-freeness forces that Bi∖x,Bi+2∖z=Bi+1,Bi+3=∅. Let T=x,z, then R\T≅KC4 (or KC4−e) and χT≤2.Ifp=4, then there exist x,x′∈B0,y,y′∈B1,z,z′∈B2,w,w′∈B3 such that xy,y′z′,zw,w′x′∉EG (it is possible that x=x′,y=y′,z=z′, and w=w′). Since B0∖x≠∅, B1∖y′≠∅ and B2∖z≠∅, the W4-freeness forces that B1∖x,B2∖z=B1∖y′,B3=∅. If z=z′, let T=x,z. If z≠z′, then xz∉EG or else x,v1,v2,z,y″≅W4 (where y″=y′ if y≠y′, y″∈B2∖y otherwise), and let T=x,y′,z. For each case, we have that R\T≅KC4 (or KC4−e) and χT≤2.R 3.17. If Bi≥2 for each i∈0,1,2,3 and m0=m1=m2=m3=1, then A=∅.Proof of R 3.17. Since m0=m1=m2=m3=1, each Bi for i∈0,1,2,3 is complete. By R 3.13 and R 3.14, we need only to prove that B0∪B1∪B2∪B3 contains either C4 or C5 as it is an induced subgraph. By R 3.10, Bi∪Bi+1≅Kt (or Kt−e) for i∈0,1,2,3. For x∈B1, there exists y∈B2,w∈B0 such that xy,xw∈EG since B2≥2 and B0≥2. The W4-freeness forces that yw∉EG. If there exists z∈B3 such that yz,wz∈EG, then x,y,z,w≅C4. Otherwise, either yz,wz∉EG or there exactly one of yz,wz belongs to EG. For the former, there must be z′∈B3\z such that yz′,wz′∈EG; that is, x,y,z′,w≅C4. For the latter, without loss of generality, yz∉EG and wz∈EG, there must be y′∈B2\y such that y′z∈EG. Then, x,y′,z,w≅C4 when xy′∈EG, and x,y,y′,z,w≅C5 when xy′∉EG.R 3.18. If Bi≥2 for each i∈0,1,2,3 and mj:mj=2,0≤j≤3≤1, then χG≤3ωG.Proof of R 3.18. Let V1=C1∪C3∪B2′∪v1,v3,V2=C2∪C0∪B1′∪v2,v0,V3=B0∪B1∪B2∪B3. Then VG=V1∪V2∪V3∪M∪A. By R 3.4, R 3.5, and R 3.7, V1 and V2 are both perfect graphs. Thus, χVk=ωVk≤ωG−1 for k=1,2. By R 3.1, χM=1.
Ifmj|mj=2,0≤j≤3=1, then V3≅C5 by R 3.12. Thus, A=∅ by R 3.14. Since ωG≥2,(24)χG≤∑l=13χVl+χM≤2ωG−1+χC5+1=2ωG+2≤3ωG.
Otherwise,mj|mj=2,0≤j≤3=0. By R 3.5, m0=m1=m2=m3=1. It follows from R 3.16 that there exists T⊂V3 such that V3\T≅KC4 (or KC4−e) where χT≤2. Since KC4 (or KC4−e) is a perfect graph and ωV3∖T≤ωG−1,(25)χV3≤χV3∖T+χT≤ωG−1+2=ωG+1.
It follows from R 3.17 thatA=∅. Therefore,(26)χG≤∑l=13χVl+χM≤2ωG−1+ωG+1+1≤3ωG.
IfωG≤2, then G is K3,P2∪P3-free, and it follows from Theorem 1 that χG≤3ωG. If ωG≥3, then 25ωG−1/4+1≤3ωG. By R 3.11, R 3.15, and R 3.18, χG≤3ωG.
The Proof of Theorem 3 is complete.


## 4. Conclusion

Gyárfás introduced the concept of theχ-bound with χ-binding functions thereby extending the notion of perfectness. There are a number of challenging conjectures about the χ-bound. In this paper, we discuss the values of the chromatic number and obtain an upper bound for the chromatic number of the graphs which are either triangle-free and P2∪P3-free or W4-free and P2∪P3-free. The iterative method plays an important role in the investigation of several properties of graphs with heritability, and it is used to prove our two theorems.



---

*Source: 2071887-2022-06-08.xml*