On graphs with no induced five-vertex path or paraglider
Shenwei Huang T. Karthick







On graphs with no induced five-vertex path or  paraglider
    
Shenwei HuangCollege of Computer Science, Nankai University, Tianjin 300350, China.
This research is partially supported by the National Natural Science Foundation of China (11801284).
T. KarthickComputer Science Unit, Indian Statistical
Institute, Chennai Centre, Chennai 600029, India. This research is partially supported by SERB-DST, Government of India under MATRICS scheme.
    December 30, 2023
================================================================================================================================================================================================================================================================================================================================================================================================







  Given two graphs H_1 and H_2, a graph is (H_1, H_2)-free if it contains no induced subgraph isomorphic to H_1 or H_2.
For a positive integer t, P_t is the chordless path on t vertices. A paraglider is the graph  that consists of a chorless cycle C_4 plus a vertex adjacent to three vertices of the C_4.
   In this paper, we study the structure of (P_5, paraglider)-free graphs, and show that every such  graph G satisfies χ(G)≤⌈3/2ω(G) ⌉, where χ(G) and ω(G) are the chromatic number
and clique number of G, respectively.  Our bound is attained by the complement of the Clebsch graph on 16 vertices.
More strongly, we completely characterize all the (P_5, paraglider)-free graphs G that satisfies χ(G)> 3/2ω(G).
We also construct an infinite family of (P_5, paraglider)-free graphs such that every graph G
in the family has χ(G)=⌈3/2ω(G) ⌉-1. This shows that our upper bound is optimal
up to an additive constant and that there is no (3/2-ϵ)-approximation algorithm to the chromatic number of (P_5, paraglider)-free graphs for any ϵ>0.


Keywords. P_5-free graphs; Chromatic number; Clique number. 



§ INTRODUCTION

Graphs in this paper are simple and finite. Given a positive integer ℓ, we denote the path on ℓ vertices by
P_ℓ, and we denote the complete graph on ℓ vertices by K_ℓ. For an integer ℓ≥ 3, C_ℓ is the cycle on ℓ vertices.
A paraglider is the graph   that consists of a C_4 plus a vertex
adjacent to three vertices of the C_4.    Given two graphs G and H, we denote by G∪ H the disjoint union of G and H, and  by G+H the join of G and H.  The
union of k copies of the same graph G will be denoted by kG; for
example 2K_2 denotes the graph that consists in two disjoint copies
of K_2. The complement of a graph G is denoted by G.  A hole (antihole) in a graph is an induced subgraph that is isomorphic to C_ℓ (C_ℓ) with ℓ≥ 4, and ℓ is the
length of the hole (antihole).  A hole or an antihole is odd if ℓ is odd.
Given a family of graphs H, a graph G is F-free if no induced subgraph of G is isomorphic to a member of
F; when F has only one element H we say that G
is H-free; when F has two elements H_1 and H_2, we simply write G is (H_1,H_2)-free instead of {H_1,H_2}-free.


For any integer k, a k-coloring of a graph G is a mapping
ψ:V(G)→{1,…,k} such that  ψ(u)≠ψ(v) whenever u and v are adjacent in G.  A graph is k-colorable
if it admits a k-coloring.  The chromatic number χ(G) of
a graph G is the smallest integer k such that G is
k-colorable.
   A clique in a graph
G is a set of pairwise adjacent vertices, and the clique number of G, denoted by ω(G), is the size of a maximum clique in G.
Obviously χ(H)≥ω(H) for every induced subgraph H of G.
A graph G is perfect if every induced subgraph H of G
satisfies χ(H) = ω(H).  Chudnovsky et al. <cit.> showed that a graph is perfect   if and only if it does not contain an odd hole or an odd antihole as an induced subgraph, and is known as the Strong Perfect Graph Theorem (SPGT).
A class of graphs G is said   to be χ-bounded <cit.>
if there is a function f (called a χ-binding function) such that  every  G∈G
satisfies χ(G)≤ f(ω(G)). For instance, the class of perfect graphs is χ-bounded with identity function f(x)=x as the χ-binding function. In fact, several classes of graphs are known to be χ-bounded; see <cit.>.



  Gyárfás <cit.> studied the χ-boundedness for the class of P_t-free graphs, and showed that every P_t-free graph G has χ(G) ≤  (t-1)^ω(G)-1. It is well known that for t≤ 4, P_t-free graphs are perfect.  The problem of
determining whether the class of P_t-free graphs (t≥ 5) admits a polynomial
χ-binding function remains open,  and seems to be difficult even when t=5. Moreover, the existence of polynomial χ-binding function for the class of P_t-free graphs (t≥ 5) would imply the Erdös-Hajnal conjecture for P_t-free graphs; see <cit.>. The best known χ-binding
function f for  the class of P_5-free graphs   satisfies c(ω^2/log w)≤
f(ω)≤ 2^ω; see <cit.>.
Here we are interested in   χ-binding functions for the class of  (P_5, H)-free graphs, for various graphs H. Recently, Brause et al. <cit.> showed that the class of (2K_2, 3K_1)-free graphs does not admit a linear χ-binding function. It follows that the class of (P_5, H)-free graphs, where H is any P_5-free graph with independence number α(H) ≥ 3, does not  admit a linear χ-binding function.  Thus it is interesting to the study  of χ-boundedness for the class of (P_5, H)-free graphs where α(H) ≤ 2.
Choudum et al. <cit.> showed that every (P_5, C_4)-free graph G satisfies χ(G)≤⌈5ω(G)/4⌉, and that every (P_5, K_1+C_4)-free graph G satisfies χ(G)≤ 5⌈5ω(G)/4⌉.
It is shown in <cit.> that every (P_5, diamond)-free graph G satisfies χ(G)≤ω(G)+1, and in <cit.> that every (P_5, paw)-free graph G satisfies χ(G)≤ω(G)+1.
Chudnovsky and Sivaram <cit.> showed that every (P_5, C_5)-free graph G satisfies χ(G) ≤ 2^ω(G)-1. Fouquet
et al. <cit.> proved that there are infinitely many (P_5, P_5)-free graphs G with χ(G)≥ω(G)^μ, where μ= log_25-1, and that every (P_5, P_5)-free graph G satisfies χ(G)≤ω(G)+12.   Very recently, Chudnovsky et al. <cit.> showed that  every (P_5, K_1+P_4)-free graph G satisfies χ(G)≤⌈5ω(G)/4⌉. We refer to a recent comprehensive survey of Schiermeyer and Randerath <cit.> for more results.


In this paper, we study the structure of the class of  (P_5, paraglider)-free graphs, and show that every such graph G satisfies χ(G)≤⌈3ω(G)/2⌉.  Our bound is attained by the complement of the well-known 5-regular Clebsch graph on 16 vertices. More strongly, we completely characterize all the (P_5, paraglider)-free graphs G that satisfies χ(G)> 3/2ω(G).
We also construct an infinite family of (P_5, paraglider)-free graphs such that every graph G
in the family has χ(G)=⌈3/2ω(G)⌉-1. This shows that our upper bound is optimal
up to an additive constant, and that there is no (3/2-ϵ)-approximation algorithm  to the chromatic number of  (P_5, paraglider)-free graphs
for any ϵ>0. Moreover, our results  generalizes the   results known on the existence of linear χ-binding functions for (P_5, C_4)-free graphs,  (P_5, paw)-free graphs,  (P_5, diamond)-free graphs, and for (3K_1, paraglider)-free graphs <cit.>.




§ NOTATIONS AND PRELIMINARIES


We use standard notation and terminology.
 In a graph G, the neighborhood of a vertex x is the set
N_G(x)={y∈ V(G)∖{x}| xy∈ E(G)}; we drop the
subscript G when there is no ambiguity.  The non-neighborhood of a vertex x is the set V(G) (N(x)∪{x}), and is denoted by N(x).   A vertex is
universal if it is adjacent to all other vertices.  Two non-adjacent vertices u and v in a graph G are comparable
if N(u) ⊆ N(v) or N(v) ⊆ N(u).   For any x∈ V(G) and A⊆
V(G)∖ x, we let N_A(x) = N(x)∩ A. Let X be a subset of V(G). We denote by G[X]
 the subgraph induced by X in G. For simplicity, we write G X instead of G[V(G) X]. Further if X is singleton, say {v}, we write G-v instead of G{v}.   For any two subsets
X and Y of V(G), we denote by [X,Y], the set of edges that has
one end in X and other end in Y.  We say that X is
complete to Y or [X,Y] is complete if every vertex in X
is adjacent to every vertex in Y; and X is anticomplete to
Y if [X,Y]=∅.  If X is singleton, say {v}, we simply
write v is complete (anticomplete) to Y instead of writing {v}
is complete (anticomplete) to Y.     We
say that a subgraph H of G is dominating if every vertex in
V(G)∖ V(H) is a adjacent to a vertex in H.  A
clique-cutset of a graph G is a clique K in G such that
G ∖ K has more connected components than G. An atom is a
connected graph without a clique-cutset.

 A
stable set is a set of pairwise non-adjacent vertices.
  We say that two sets meet if their
intersection is not empty.
In a graph G, we say that a stable set is good if it meets
every clique of size ω(G).




An expansion of a graph H is any graph G such that V(G) can
be partitioned into |V(H)| non-empty  sets
Q_v, v∈ V(H), such that [Q_u,Q_v] is complete if uv∈ E(H),
and [Q_u,Q_v]= if uv∉ E(H). An expansion of a graph is a clique expansion if each Q_v is a clique,
 is a P_3-free expansion if each Q_v induces a P_3-free graph, and is a perfect expansion if each Q_v induces a perfect graph. By a classical result of Lovász <cit.>, any perfect expansion of a  perfect graph is perfect. In particular, any P_3-free expansion of a perfect graph is perfect.





Let G^*,F_1,F_1',F_2,F_3 be five graphs as shown in
Figure <ref>.



 Let H be the class of graphs G such that V(G) can be partitioned into five sets Q_1, Q_2, R_1, R_2, S such that:
=1pt

  * Q_1={a_1,a_2…, a_k}, Q_2={b_1,b_2,…,b_k} (where k≥ 2),  S are cliques, [Q_1, Q_2] is a perfect matching, say
 {a_1b_1,a_2b_2,…,a_kb_k}  and |S|≤ k.

  * G[R_1] and G[R_2] are perfect.

  * [Q_1, R_1], [Q_2, R_2] are complete, [Q_1∪ R_1, R_2] = and [Q_2∪ R_2, R_1]=.


  * [S, R_1∪ R_2] is complete.


  * There exists an injective function f:S→{1,2,…, k} such that for each vertex  x∈ S, {x} is anti-complete to {a_f(x), b_f(x)}, and is complete to (Q_1∪ Q_2) {a_f(x), b_f(x)}.

  * No other edges in G.

Clearly, the graphs C_6 and F_2 belong to H. See   Section 4 for more examples.


We will use
the following theorem of Brandstädt and Hoàng <cit.>.


Let G be a (P_5, paraglider)-free atom that has no universal or pair of comparable vertices.  Then
either G is G^* or  every induced C_5 in G is dominating. 





§ STRUCTURE OF (P_5, PARAGLIDER)-FREE GRAPHS

In this section, we prove the following structure theorem for the class of (P_5, paraglider)-free graphs.

Let G be a (P_5, paraglider)-free atom with no universal or pair of comparable vertices.
 Then one of the following hold:
=0pt

  * G is an induced subgraph of the complement of the Clebsch graph.

  * G is a P_3-free expansion of C_5.

  * G has a stable set S such that either S is good or G S is perfect.

  * G∈H.


 If G is G^*, then S:={v_7,v_8} is a stable set such that G S ≅C_6 is perfect. If G is perfect, then any color class in a χ(G)-coloring of G is a good stable set. So we may assume that G is not G^*, and is not perfect. Now since
a P_5-free graph contains no hole of length at least 7, and a paraglider-free graph
contains no antihole of length at least 7, it follows by the Strong Perfect Graph Theorem <cit.> that G contains a hole of length 5. That is, G contains a C_5 as an induced subgraph. Now the theorem follows from Theorem <ref>, and from Theorems <ref>, <ref>, <ref> and Theorem <ref> given below.





In the next theorem, we make some general observations about the
situation when a (P_5, paraglider)-free graph contains a hole (which must
have length 5).

Let G be any (P_5, paraglider)-free graph that contains a C_5 with
vertex-set C={v_1,…,v_5} and {v_iv_i+1| i∈{1,…,5}, i 5}. Suppose that G is an atom and has no pair of comparable vertices. Let:

    T_i    =   {x∈ V(G) C| N_C(x)={v_i, v_i+1, v_i+3}}. 
    
    X_i    =   {x∈ V(G) C| N_C(x)={v_i-1, v_i+1}}. 
    
    Y_i    =   {x∈ V(G) C| N_C(x)={v_i-1, v_i, v_i+1}}.
    
    Z_i    =   {x∈ V(G) C| N_C(x)= C∖{v_i}}.
    
    A    =   {x∈ V(G) C| N_C(x)=C}.

Moreover, let T = T_1∪⋯∪ T_5, X =
X_1∪⋯∪ X_5, Y = Y_1∪⋯∪ Y_5, and Z = Z_1∪⋯∪ Z_5. Then the following properties hold for all i, i  5:

=1pt

  *  G[C] is a dominating induced subgraph of G and V(G) = C∪ A ∪ T∪ X ∪ Y ∪ Z.


  * (a) |T_i|≤ 1. If |T_i|= 1, then we denote T_i by {t_i}.
 (b) [T_i, T_j]=∅, for every j; so T is an independent set.
    (c) [T_i, X_i+3] is complete, and [T_i, X_j]=, for every j≠ i+3.


  *   (a) X_i is an independent set.
 (b) [X_i, X_i+1] is complete.
  (c) |[X_i, X_i+2]|≤ 1. 
(d) If X_i+1≠, then [X_i, X_i+2]=.




  *  (a) G[Y_i] is (K_2∪ K_1)-free. Hence G[Y_i] is a complete multi-partite graph.
 (b) [Y_i, Y_i+1] is complete.
 (c) If [Y_i,Y_i+2]≠, then [Y_i, Y_i+2] is a matching.
 (d) If Y_i≠, then Y_i-1 and Y_i+1 are cliques.
 (e) If y∈ Y_i and if [{y}, Y_i+2] is complete, then |Y_i+2|≤ 1. More generally, if [Y_i, Y_i+2] is complete, then |Y_i|≤ 1 and |Y_i+2|≤ 1.


  *  (a) |Z_i|≤ 1. If |Z_i|= 1, then we denote Z_i by {z_i}.
 (b) [Z_i, Z_i+1]=.
 (c) [Z_i, Z_i+2] is complete.

 
  *  (a) [X_i, Y_i∪ Y_i+1∪ Y_i-1∪ (Z Z_i)] is complete.
 (b)  [X_i, Y_i-2∪ Y_i+2∪ Z_i]=.


  *  (a) [Z_i, Y_i ∪ Y_i-2∪ Y_i+2] is complete.
 (b)  [Z_i, Y_i-1∪ Y_i+1]=.




  *   (a)  A is a clique. 
 (b) [A, V(G) (A∪ Y)] is complete.



  *  Suppose that T_i≠. Then:
 
 (a) The sets T_i-1∪ T_i+1, Y, Z Z_i+3 are empty.
 (b) [X_i, X_i+2], [X_i+1, X_i-1] and [T_i, Z_i+3] are empty.




  *  Let x, y∈ V(G) and q∈ A. Then the following hold:
 (a) If x∈ Y_i and y∈ Y_i+1∪ Y_i+2 are adjacent, then q is either complete or anti-complete to {x, y}. 

    (b) If x∈ Y_i and y∈ Y_i+2 are not adjacent, then q is adjacent one of x, y.

(c) If x∈ Y_i and y∈ Y_i are  adjacent, then q is adjacent to one of x,  y.

(d) N(q)∩ Y_i is a stable set.


  *  Suppose that G is F_1-free. Then [X_i, X_i+2∪ X_i-2∪ Y_i+2∪ Y_i-2] =, and hence
 X=.






 Let G be the given graph with vertex-set V and edge-set E.

 Proof of (R<ref>). Since G has no clique cut-set, by Theorem <ref>, G[C] is dominating, and so every vertex in V C has a neighbor in C. Now (R<ref>) follows since G is P_5-free. Indeed if a vertex x∈ V C has exactly one neighbor (say, v_i) or has exactly two neighbors that are consecutive (say, v_i and v_i+1) in C, then x-v_i-v_i-1-v_i-2-v_i-3 is a P_5. ♢

Proof of (R<ref>). (a): Otherwise, for any two vertices x and y in T_i, either {x,v_i+1, v_i+2,v_i+3,y}
or {x,v_i,y,v_i+3,v_i+1} induces a paraglider. So (a) holds.  


(b): Suppose to the contrary that there are adjacent vertices x∈ T_i and y∈ T_j.  Now if j≠ i-1, then {x,v_i+1,v_i+2,v_i+3,y} induces a paraglider, and if  j= i-1, then {y,v_i,v_i+1,v_i+2,x} induces a paraglider, a contradiction. This proves item (b).


(c): Pick a vertex x∈ T_i and a vertex y∈ X_j. Up to symmetry, we may assume that j∈{i,i+2,i+3}.
  If j=i, then xy∉ E, for otherwise {y,v_i+1,v_i,v_i-1,x} induces a paraglider.
If j=i+2,  then xy∉ E, for otherwise {x,v_i+1,v_i+2,v_i+3,y} induces a paraglider.
If j=i+3, then xy∈ E, for otherwise v_i-x-v_i+3-v_i+2-y is a P_5.   Since this
holds for any x and y, it proves item (c). ♢

Proof of (R<ref>). (a): Otherwise, for any two adjacent vertices x and y in X_i, {x,v_i+1,v_i,v_i-1,y}
induces a paraglider. So (a) holds. 


(b): Suppose not, and let x∈ X_i and y∈ X_i+1 be not adjacent. Then x-v_i-1-v_i-2-v_i-3-y is a P_5. So (b) holds. 


(c): We may assume that [X_i,X_i+2]≠. We first claim that [X_i,X_i+2] is a matching. Suppose not. Then, up to symmetry, we may assume that there exist vertices x∈ X_i and y,z∈ X_i+2 such that xy,xz∈ E. By (a), yz∉ E. But then {x,z,v_i+3,y,v_i+1} induces a paraglider. So [X_i,X_i+2] is a matching. Now, if |[X_i,X_i+2]|≥ 2, then there exist matching edges e,f∈ [X_i,X_i+2], say e:=xy and
f:=x'y' with x,x'∈ X_i and y,y'∈ X_i+2. By (a), we have xx'∉ E and yy'∉ E.  But then y-x-v_i-1-x'-y' is a P_5, a contradiction. This proves item (c). ♢

Proof of (R<ref>). (a):  Suppose to the contrary that G[Y_i] contains an induced K_2∪ K_1 with vertex-set {x,y,z} and edge-set {xy}. Then {x, v_i-1,z,v_i+1,y} induces a paraglider, which is a contradiction. So (a) holds.  


(b): Suppose not, and let x∈ Y_i and y∈ Y_i+1 be not adjacent. Then x-v_i-1-v_i-2-v_i-3-y is a P_5. So (b) holds. 


(c): Suppose not. We may assume, up to symmetry, that x∈ Y_i and y,z∈ Y_i+2 such that xy,xz∈ E. Then {x,y,v_i-2,v_i-1,z} or
{x,y,v_i-2,z,v_i+1} induces a paraglider, a contradiction. This proves item (c).


(d): Let x∈ Y_i. Suppose to the contrary  that there are non-adjacent vertices y and z in Y_i+1.  By (b), xy,yz∈ E. But then {x,y,v_i+2,z,v_i} induces a paraglider which is a contradiction. So Y_i+1 is a clique. Likewise, Y_i-1 is a clique. This proves item (d). 


(e):  This follows by item (c). ♢

Proof of (R<ref>). (a): Otherwise, for any two vertices x and y in Z_i, either {v_i,v_i+1, x,v_i-1,y}
or {x,v_i+1,y,v_i-1,v_i+2} induces a paraglider.   


(b): Suppose not, and let x∈ Z_i and y∈ Z_i+1 be   adjacent. Then {v_i,v_i+1, v_i+2,y,x} induces a paraglider.  


(c): Suppose not, and let x∈ Z_i and y∈ Z_i+2 be not adjacent. Then {v_i,v_i+1, x,v_i-1,y} induces a paraglider.
 ♢

Proof of (R<ref>). (a): Suppose not, and  let x∈ X_i and y∈ Y_i∪ Y_i+1∪ Y_i-1∪ (Z Z_i) be non-adjacent. By symmetry, we may assume that y∈ Y_i∪ Y_i+1∪ Z_i-1∪ Z_i+2. Now if y∈ Y_i∪ Z_i+2, then {x,v_i+1,y,v_i-1,v_i} induces a paraglider, and if y∈ Y_i+1∪ Z_i-1, then x-v_i-1-v_i-y-v_i+2 is a P_5, a contradiction. This proves item (a).


(b): Suppose not, and let x∈ X_i and y∈ Y_i-2∪ Y_i+2∪ Z_i be adjacent. By symmetry, we may assume that y∈ Y_i+2∪ Z_i.
Now if y∈ Y_i+2, then v_i-v_i-1-x-y-v_i+2 is a P_5, and if y∈ Z_i, then {x,v_i+1,v_i,v_i-1,y} induces a paraglider, a contradiction. This proves item (b). ♢

Proof of (R<ref>). (a): Suppose not. Up to symmetry, we may assume that there are non-adjacent vertices x∈ Z_i and y∈ Y_i∪ Y_i+2. Now if y∈ Y_i, then {v_i,v_i+1,x,v_i-1,y} induces a paraglider, and if y∈ Y_i+2, then v_i-v_i-1-x-v_i+2-y is a P_5, a contradiction. This proves item (a).


(b): Suppose not, and let x∈ Z_i and y∈ Y_i+1∪ Y_i-1 be adjacent. Then {v_i,v_i+1,x,v_i-1,y} induces a paraglider. ♢

Proof of (R<ref>). Suppose not, and let x∈ A and y∈ A ∪ (V(G) Y) be non-adjacent.
 If y∈ A, then {x,v_i,y,v_i+3,v_i+1} induces a paraglider. So let us assume that  y∈ V(G) Y.
 Then there exist j∈{1,…,5}, j modulo 5 such that yv_j,yv_j+2∈ E and yv_j+1∉ E. But then
 {y,v_j,v_j+1,v_j+2,x} induces a paraglider, a contradiction. ♢

Proof of (R<ref>). Let x∈ T_i.


(a): Suppose to the contrary that there exists a vertex y∈ T_i+1∪ T_i-1∪ Y∪ (Z Z_i+3).
First suppose that y∈ T_i+1∪ Y_i ∪ Z_i.  Then since y-v_i-x-v_i+3-v_i+2 or
x-v_i-v_i-1-y-v_i+2 is not a P_5, we have xy∈ E. But then {v_i,v_i+1,y,v_i-1,x} or {x,v_i,v_i-2,v_i-1,y} induces a a paraglider.  So y∉ T_i+1∪ Y_i ∪ Z_i. Likewise, y∉ T_i-1∪ Y_i+1∪ Z_i+1.
Next suppose that y∈ Y_i+2. Then since {x,v_i+1,v_i+2,v_i+3,y} does not induce a paraglider, we have xy∈ E. But then v_i-1-v_i-x-y-v_i+2 is a P_5. So  y∉ Y_i+2. Likewise, y∉ Y_i-1.
Next suppose that y∈ Y_i-2. Then since {x,v_i,v_i-1,v_i-2,y} does not induce a paraglider, xy∉ E. But then x-v_i-v_i-1-y-v_i+2 is a P_5. So y∉ Y_i-2. Finally, suppose that y∈ Z_i+2∪ Z_i-1. Up to symmetry, we may assume that y∈ Z_i+2. Then since {x,v_i,v_i-1,v_i-2,y} does not induce a paraglider, we have xy∈ E. But then {x,v_i+1,v_i+2,v_i+3,y} induces a paraglider, a contradiction. This proves item (a).


(b): Suppose that there is an edge yz in one of the listed sets.  If y∈ X_i and z∈ X_i+2, then by (R<ref>:c), we have xy,xz∉ E; and then z-y-v_i-1-v_i-x is a P_5.  If y∈ X_i+1 and z∈ X_i-1, then by (R<ref>:c), we have xy,xz∉ E; and then x-v_i+1-v_i+2-y-z is a P_5. If y∈ T_i and z∈ Z_i+3, then {y,v_i,v_i-1,v_i-2,z} induces a paraglider. These contradictions show that (b) holds.   ♢

Proof of (R<ref>). (a): Suppose not. Up to symmetry, we may assume that qx∈ E and qy∉ E. Then either {q,x,y,v_i+2,v_i} or {v_i-1,x,y,v_i-2,q} induces a paraglider, a contradiction.  So (a) holds. 


(b): Otherwise, x-v_i-q-v_i+2-y is a P_5.


(c): Otherwise, {x,v_i+1,q,v_i-1,y} induces a paraglider.


(d): This follows by item (c).  ♢



Proof of (R<ref>). Suppose to contrary that there are adjacent vertices x∈ X_i and y∈ X_i+2∪ X_i-2∪ Y_i+2∪ Y_i-2. We may assume, up to symmetry, that y∈ X_i+2∪ Y_i+2. Now {v_i,v_i+1,y,v_i-2,v_i-1,x} induces an F_1, a contradiction. So, [X_i, X_i+2∪ X_i-2∪ Y_i+2∪ Y_i-2]=.

Now we show that X=. Suppose to the contrary that X≠ and let x∈ X, say x∈ X_i for some i. We claim that x and v_i are comparable.  Since G is F_1-free, T=. Now by the preceding point, by the definition of X_i, and by (R<ref>),(R<ref>), (R<ref>:b), and since G[C] is dominating, we see that N_G(x)={v_i+1,v_i-1}∪ X_i+1∪ X_i-1∪ Y_i ∪ Y_i+1∪ Y_i-1∪ (Z Z_i)∪ A, and N_G(x)={v_i+2,v_i-2}∪ (X_i{x})∪ X_i-2∪ X_i+2∪ Y_i+2∪ Y_i-2∪ Z_i.
So, N_G(x)= N_G(v_i) and N_G(x)=N_G(v_i), and hence we  conclude that x and v_i are comparable, a contradiction. So (R<ref>) holds. ♢

This completes the proof of Theorem <ref>.






Let G be a (P_5, paraglider)-free atom with no universal vertex.
Suppose that G contains   F_1. Then G has a stable set S such that G S is a bipartite graph or a bull. In particular, G S is perfect.


 Let G be the given graph with vertex-set V and edge-set E.
First suppose that G contains an F_1'.  Consider the graph F_1' as shown in Figure <ref> and let
C={v_1,…, v_5}.  We use the same notation as in
Theorem <ref> and use the properties in Theorem <ref>.  Then by (R<ref>:a), T_1 = {t_1} and T_3={t_3}.
Moreover, by (R<ref>:a), T={t_1, t_3}, Y= and Z=.
Then since Y=,   any vertex in A is a universal vertex of G (by (R<ref>)), and hence A=.
Also, by (R<ref>:b), [X_1,X_3]= and [X_2,X_4]=.
Now, let us define  S:= {t_1, t_3, v_5}∪ X_5, S_1:={v_1,v_3}∪ X_1∪ X_3, and S_2:={v_2,v_4}∪ X_2∪ X_4.
Then by (R<ref>:a)  and (R<ref>:c), the set S:= {t_1, t_3, v_5}∪ X_5 is a stable set. Also, by the preceding points and (R<ref>:a), we see that V(G) S = S_1∪ S_2, and S_1 and S_2 are stable sets. Hence G S is bipartite.


Suppose that G contains no F_1'. Consider the graph F_1 as shown in Figure <ref> and let
C={v_1,…, v_5}.  We use the same notation as in
Theorem <ref> and use the properties in Theorem <ref>.  Since G has no F_1', by (R<ref>:a), T = {t_1}.  Then by (R<ref>), the sets Y, Z Z_4, [X_2,X_5] and [{t_1}, Z_4] are empty.  Then since Y=,   any vertex in A is a universal vertex of G (by (R<ref>)), and hence A=. Also, if there are adjacent vertices x_2∈ X_2 and x_4∈ X_4, then {v_1,v_2,v_3,x_4,v_5,t_1,x_2} induces an F_2.
So [X_2,X_4]=. Likewise, [X_3,X_5]=.

Suppose that Z_4=. Then let us define  S:= {t_1, v_3, v_5}∪ X_3∪ X_5, S_1:={v_1}∪ X_1, and S_2:={v_2,v_4}∪ X_2∪ X_4.
Then by (R<ref>:a)  and (R<ref>:c), the set S:= {t_1, t_3, v_5}∪ X_5 is a stable set. Also, by the preceding points and (R<ref>:a), we see that V(G) S = S_1∪ S_2, and S_1 and S_2 are stable sets. Hence G S is bipartite.


 So let us assume that Z_4≠, and by (R<ref>:a), Z_4={z_4}. Then by (R<ref>:b), t_1z_4∉ E(G). Now we claim that X_j=, for j≠ 4. Suppose not. Up to symmetry, we may assume that there exists a vertex x∈ X_1∪ X_3. If x∈ X_1, then by (R<ref>:c) and (R<ref>:a), we have t_1x∉ E and xz_4∈ E. But then v_4-t_1-v_1-z_4-x is a P_5.   If x∈ X_3, then since {v_2,v_3,v_4,x,z_4} does not induce a paraglider, xz_4∉ E. But then x-v_4-v_3-z_4-v_1 is a P_5. So, we conclude that X_j=, for j≠ 4.  Now, by (R<ref>:a) and (R<ref>:b), the set S:={z_4,v_4}∪ X_4 is a stable set such that G S:=G[{t_1,v_5,v_1,v_2,v_3}] is a bull.  This completes the proof of the theorem.








Let G be a (P_5, F_1, paraglider)-free atom with no  universal or pair of comparable vertices. Suppose that G contains F_2.  Then one of the following hold:
=0pt

  * G is an induced subgraph of the complement of the Clebsch graph.

  * G has a good stable set.

  * G ∈H.



 Let G be the given graph with vertex-set V and edge-set E.
Consider the graph F_2 as shown in Figure <ref> and let
C={v_1,…, v_5}.  We use the same notation as in
Theorem <ref> and use the properties in Theorem <ref>.
 So y_2∈ Y_2 and y_5∈ Y_5, and y_2y_5∈ [Y_2, Y_5]. Let {a_1b_1,a_2b_2,…,a_kb_k} denote the edges of [Y_2,Y_5], and let a_1b_1:= y_2y_5. Moreover, let Y_2^*:= Y_2{a_1}, Y_2':= Y_2{a_1,a_2,…,a_k}, Y_5^*:= Y_5{b_1} and Y_5'=Y_5{b_1,b_2,…,b_k}.

Since G is F_1-free, T=, and by (R<ref>), X=. Then we have the following:

 

For each i∈{1,2,…,k}, the following hold:

 
  * Any vertex in Y_2{a_i} is adjacent to a_i and non-adjacent to b_i (and similarly, any vertex in Y_5{b_i} is adjacent to b_i and non-adjacent to a_i). In particular, {a_1,…,a_k} and {b_1,…,b_k} are cliques.
      
  * [Y_3, {b_i}] is complete and [Y_4, {a_i}] is complete.

  * [Y_3, Y_5{b_i}]= and [Y_4, Y_2{a_i}]=.
 
  * Any vertex a∈ A is either complete to {a_i, b_i} or anti-complete to {a_i, b_i}. Moreover, if a∈ A and if there exists an index i such that a is anti-complete to {a_i, b_i}, then a is complete to (Y_2{a_i}) ∪ (Y_5{b_i}).
 
 
  (i): Let x∈ Y_2{a_i} be arbitrary. If xa_i∉ E, then since {x,v_1,a_i,v_3,b_i} does not induce a paraglider, we have xb_i∉ E, and then x-v_2-a_i-b_i-v_5 is a P_5. So, xa_i∈ E. Moreover, since {x,v_3,v_4,b_i,a_i} does not induces a paraglider, we have xb_i∉ E. Thus any vertex in Y_2{a_i} is adjacent to a_i and non-adjacent to b_i. Likewise, any vertex in Y_5{b_i} is adjacent to b_i and non-adjacent to a_i. So (i) holds. 

 
 (ii): If there is a vertex x∈ Y_3 such that xb_i∉ E, then by (R<ref>:b), xa_i∈ E, and then {a_i,v_3,v_4,b_i,x} induces a paraglider which is a contradiction. So [Y_3, {b_i}] is complete. Likewise, [Y_4, {a_i}] is complete. Thus (ii) holds.

 
 (iii): Suppose to the contrary that there are adjacent vertices x∈ Y_3 and y∈ Y_5{b_i}.
  By item (i), we have yb_i∈ E, and by item (ii), xb_i∈ E. Now, {x,y,v_1,v_2,b_i} induces a paraglider which is a contradiction. So (iii) holds. 

 
 (iv): This follows by item (i), (R<ref>:a) and  (R<ref>:b).
 

Next we have the following:
 
 Y_1 is a clique, |Y_3|≤ 1, |Y_4|≤ 1, and [Y_1, Y_3∪ Y_4] is complete.
 

 First, since y_2∈ Y_2 and y_5∈ Y_5, by (R<ref>:d), Y_1 is a clique.
 Next, we know by Claim <ref>(ii) that [Y_3,{b_1}] and [Y_4, {a_1}] are  complete. So by (R<ref>:e), we have |Y_3| ≤ 1 and  |Y_4|≤ 1. Finally, suppose to the contrary that there are non-adjacent vertices y_1∈ Y_1 and y_3∈ Y_3. We know by (R<ref>:b) that y_1b_1∈ E, and by Claim <ref>(ii) that y_3b_1∈ E. Now {b_1,v_1,v_2,y_3,y_1} induces a paraglider, a contradiction. So [Y_1, Y_3] is complete. Likewise, [Y_1, Y_4] is  complete. 

 For each i∈{1,2,…, k}, let A_i':= {x∈ A| x {a_i,b_i} (Y_2{a_i}∪ (Y_5{b_i})}. Let A':=A_1'∪⋯∪ A_k'. Let A”:= {x∈ A| x {a_1,…, a_k, b_1,…,b_k}}.
Then by Claim <ref>(iv), A= A'∪ A”.
Moreover, we have the following claim.

 The following hold:
(i) For each i∈{1,2,…, k}, |A_i'|≤ 1. (ii) [A', Y_1∪ Y_3∪ Y_4] =. (iii) [A”, Y_1∪ Y_3∪ Y_4] is complete.

 (i): Suppose to the contrary that |A_i'|≥ 2 and let x, x'∈ A_i'. Since A_i' ⊆ A and A is a clique (by (R<ref>:a), xx'∈ E. But, then {x,v_1,a_i,v_3,x'} induces a paraglider. So (i) holds.  

(ii): Suppose not. Then there are adjacent vertices q∈ A' and y∈ Y_1∪ Y_3∪ Y_4.  Since q∈ A', there exists a pair {a_i,b_i} such that q is anti-complete to {a_i,b_i}. Now if y∈ Y_1, then by (R<ref>:b), yb_i∈ E, and then {v_1,q,v_4,b_i,y} induces a paraglider which is a contradiction. So y∈ Y_3∪ Y_4. Then  since  [Y_3,{b_i}] and [Y_4,{a_i}] are complete (by Claim <ref>(ii)), we have  a  contradiction to (R<ref>:a). So (ii) holds.

(iii): Suppose not. Then there are non-adjacent vertices q∈ A” and y∈ Y_1∪ Y_3∪ Y_4. Since q∈ A”, q is complete to {a_1,b_1}. Now if y∈ Y_1, then by (R<ref>:b), yb_1∈ E, and then {v_5,y,v_2,q,b_1} induces a paraglider which is a contradiction. So y∈ Y_3∪ Y_4. Then  since  [Y_3,{b_1}] and [Y_4,{a_1}] are complete (by Claim <ref>(ii)), we have  a  contradiction to (R<ref>:a). So (iii) holds.
 


 Let x∈ A”. Then either  x is complete to Y_2 or  x is complete to Y_5.

Suppose not. Then  there exist vertices p∈ Y_2' and  q∈ Y_5' such that xp,xq∉ E. But, then p-v_2-x-v_5-q is a P_5. 

Suppose that A”≠, and let x∈ A”. By Claim <ref> and up to symmetry, we may assume that x is complete to Y_5. Then using (R<ref>) and Claim <ref> and since x is not universal, we conclude that x has a non-neighbor in Y_2. Moreover, by (R<ref>:d), N(x)∩ Y_2 is a stable set. Now let us define S:= {x}∪ (N(x)∩ Y_2). Then since [{x}, V(G) (N(x)∩ Y_2)] is complete, by (R<ref>:a), we see that S is a good stable set of G. So, we may assume that A”=.




  The following hold:  (i) If Y_2^*∪ Y_5^*≠, then Z_1=. (ii) If  Y_2^*≠, then  Y_3=. (iii) If Y_5^* ≠, then Y_4=.
  To prove the claim, we show that if Y_2^*≠, then Z_1∪ Y_3=, and the other cases follow by symmetry. Let x∈ Y_2^*.
 Suppose to the contrary that Z_1∪ Y_3≠, and let y∈ Z_1∪ Y_3. We know by Claim <ref>(i) that a_1x∈ E and b_1x∉ E. Now if y∈ Z_1, then  by (R<ref>:b), we have ya_1,yb_1,yx∉ E. But then y-v_5-b_1-a_1-x is a P_5. So y∈ Y_3. Then by (R<ref>:b), xy∈ E, and by Claim <ref>(ii), yb_1∈ E. But then {x,y,b_1,v_1,v_2} induces a paraglider which is a contradiction. So, Z_1∪ Y_3=.
 






 
 Suppose not. Let x,y∈ Y_1 and z∈ Z_1∪ Z_2∪ Z_5 ∪ A_1'. We know by Claim <ref> that Y_1 is a clique and so xy∈ E. Moreover, by (R<ref>:b), {x,y} is complete to {a_1,b_1}.  If z∈ Z_1, then zx,xy∈ E (by (R<ref>:a)), and then by (R<ref>:b), {x,z,v_3,a_1,y} induces a paraglider.
 If z∈ Z_2∪ Z_5, then zx,xy∉ E (by (R<ref>:b)). Also if z∈ Z_2, then za_1∈ E (by (R<ref>:a)), and if  z∈ Z_5, then zb_1∈ E (by (R<ref>:a)). But then either {x,v_5,z,a_1,y} or  {x,v_2,z,b_1,y} induces a paraglider.
 If z∈ A_1', then by Claim <ref>(ii), zx,zy∉ E. But then {x,v_2,z,v_5,y} induces a paraglider.




Suppose that Y_2^* ∪ Y_5^*=. Since A”=, A=A_1'.
If Y_3∪ Y_4∪ Z_1 ∪  Z_2∪ Z_5 ∪ A_1'≠ or if |Y_1|≤ 1, then by Claims <ref> and <ref>, and (R<ref>:e) we conclude that  Y is a clique with |Y|≤ 5. So |V(G)|=|V(C_5)|+ |Z|+|Y|+|A_1'|≤  16, and we see that in this case, G is an induced subgraph of the complement of the Clebsch graph.
   If Y_3∪ Y_4∪ Z_1 ∪  Z_2∪ Z_5 ∪ A_1'= and |Y_1|≥ 2, then since Y_1 is complete to {a_1,b_1} (by (R<ref>:b)), we see that ω(G)≥ 5, and hence {v_1} is a good stable set of G.


So suppose that Y_2^* ∪ Y_5^*≠. We may assume, up to symmetry, that Y_2^*≠. Let  p∈ Y_2^*.  Then by Claim <ref>, Z_1∪ Y_3 =. Further we have the following.

 
 Suppose not. Let x∈ Y_1 and y∈ Y_4∪ Z_2∪ Z_5∪ A'. Then by (R<ref>:b), xb_1, px∈ E.  Now:
  If y∈ Y_4, then yx∈ E ( by Claim <ref>), py∉ E (by Claim <ref>(iii)). But then {x,y,v_3,p,v_2} induces a paraglider.
 If y∈ Z_2, then by (R<ref>), yb_1, yp∈ E and yx∉ E. But then {p,x,v_5,y,b_1} induces a paraglider.
 If y∈ Z_5, by (R<ref>), yb_1, yp∈ E and yx∉ E. But, then {p,x,b_1,y,v_2} induces a paraglider.
So, we may assume that y∈ A'. Then there exists a pair {a_i,b_i} such that y is anti-complete to {a_i,b_i}. By Claim <ref>(i), pa_i∈ E and pb_i∉ E. Then since p-v_2-y-v_5-b_i is not a P_5, we have py∈ E. Also, by Claim <ref>, xy∉ E. But now {p,x,v_5,y,v_2} induces a paraglider which is a contradiction. So the claim holds.



First suppose that Y_1≠. Then by Claim <ref>, Y_4∪  Z_2∪ Z_5∪ A'=.  But then {v_1} is a good stable set of G. 
 So, we may assume that Y_1=.


Next suppose that Y_4≠. Then by Claim <ref>, we let Y_4={y_4}. Also, by Claim <ref>, Y_5^*=.  Moreover, we show that Z_3=. Suppose not, and let z_3∈ Z_3. Then by (R<ref>:b), z_3p,z_3y_4∉ E. But then y_4-v_4-z_3-v_1-p is a P_5. So, Z_3=. Now, in this case, we see that there is a good stable set of G as follows:
 If Z=, then {y_4,v_2} is a good stable set.  So Z≠.
  If Z_2≠, then by (R<ref>), (R<ref>:a), and (R<ref>),  [Z_2, V(G){v_2}] is complete, and hence  {z_2,v_2} is a good stable set of G. So Z_2=.
 Next if Z_4≠, then since [Z_4, V(G){v_4,b_1}] is complete,  {z_4,v_4} is a good stable set of G. So Z_4=.
  Finally, if Z_5≠, then since [Z_4, V(G){b_1}∪ Y_4] is complete, {z_5,v_5} is a good stable set of G.





So, we may assume that Y_4=. If Z_2≠,  then since   [Z_2, V(G) ({v_2}∪ Z_3)] is complete, we see that {z_2,v_2} is a good stable set of G. So Z_2=. Likewise, Z_5=.
 Then we define Q_1∪ R_1:= {a_1,a_2,…,a_k, v_2,v_3}∪ Y_2'∪ Z_4, Q_2∪ R_2:= {b_1,b_2,…,b_k,v_4,v_5}∪ Y_5'∪ Z_3,  and S:= {v_1}∪ A'. Now, it is easy see that G∈H.


 This completes the proof of the theorem.






Let G be a (P_5,F_1,F_2,paraglider)-free atom with no universal or pair of comparable vertices. Suppose that G contains  F_3. Then G has a stable set S  such that either S is good or G∖ S is  perfect.


 Let G be the given graph with vertex-set V and edge-set E.
Consider the graph F_3 as shown in Figure <ref> and let
C={v_1,…, v_5}.  We use the same notation as in
Theorem <ref> and use the properties in Theorem <ref>.  So y_1 ∈ Y_1 and z_1∈ Z_1. Since G is F_1-free, T∪ X= (by (R<ref>)). Moreover, we have the following:

 For each i, we have  [Y_i, Y_i+2]=.

 Suppose to the contrary that there are adjacent vertices, say x∈ Y_i and y∈ Y_i+2. Then {v_1,v_2,v_3,v_4,v_5,x,y} induces an F_2 which is a contradiction. So the claim holds. 


 For each i, we have either Z_i = or Y_i-1∪ Y_i+1=.

 Suppose not. Up to symmetry, let z∈ Z_i and y∈ Y_i+1. Then by (R<ref>), zy∉ E. But, then {v_1,v_2,v_3,v_4,v_5,z,y} induces an F_2. 





Since z_1∈ Z_1 and y_1∈ Y_1, by Claim <ref>, the sets Y_2, Y_5, Z_2 and Z_5 are empty. If A=, then  up to symmetry, we  have three cases: (a) Z_3≠ and Z_4 ≠. (b) Z_3≠ and Z_4=. (c) Z_3 = and Z_4 =.
In Case (a), Y_3 =Y_4 =, and hence G- {v_2, v_4} is a P_3-free expansion of a perfect graph, and hence perfect. In Case (b) and in Case (c), G-{v_2, v_5} is a P_3-free  expansion of a P_4, and hence perfect.

So suppose that A≠. First let us assume that [A, Y_1] is not complete. Then there exists a vertex x ∈ A that has a non-neighbor in Y_1, say y∈ Y_1. If x has a non-neighbor y'∈ Y_3∪ Y_4, then y-v_1-x-v_3-y' or y-v_1-x-v_4-y' is a P_5. So,  by (R<ref>), [{x}, V(G) Y_1] is complete. Then by (R<ref>:d), {x}∪ (N(x)∩ Y_1) is a good stable set of G. So we may assume that [A, Y_1] is   complete. Then since G has no universal vertex, by (R<ref>), x has a non-neighbor in Y_3∪ Y_4.  Then {x}∪ (N(x)∩ Y_3) or {x}∪ (N(x)∩ Y_4) is a good stable set of G. This complete the proof of the theorem.






Let G be a (P_5,F_1,F_2, F_3,paraglider)-free atom with no universal or pair of comparable vertices. Suppose that G contains a C_5. Then one of the following hold:
=0pt

  * G is an induced subgraph of the complement of the Petersen graph.

  * G is an P_3-free expansion of C_5.

  * G has a stable set S such that G S is perfect.




 Let G be the given graph with vertex-set V and edge-set E.
 Suppose that G contains  C_5 with vertex set C={v_1,…, v_5}.  We use the same notation as in
Theorem <ref> and use the properties in Theorem <ref>. Since G is F_1-free, T∪ X = (by (R<ref>)).
Since G is F_2-free, we have, for each i, [Y_i, Y_i+2]=. Since G is F_3-free, [A, Y] is complete. So by (R<ref>), any vertex in A is a universal vertex of G  and hence A=.  Moreover, if z_i∈ Z, then  since G is (F_2,F_3)-free, by (R<ref>), we have Y_j=, for j∈{i-1,i, i+1}.


If Z=, then G is a P_3-free expansion of C_5 (by (R<ref>)). So let us assume that Z≠.
If there exists an  i such that z_i, z_i+2∈ Z, then Y=. Now  by (R<ref>), G is an induced subgraph of the complement of the Petersen graph. Finally up to symmetry, let us assume that   Z= {z_1} or Z={z_1,z_2}. (a) If Z={z_1}, then Y_j=, for j∈{1,2,5}, and by (R<ref>), [Y_3∪ Y_4, Z] is complete. So, by (R<ref>:a), G{v_1} is  a P_3-free expansion of a perfect graph, and hence perfect. (b) If Z={z_1,z_2}, then Y_j=, for j∈{1,2,3, 5}, and by (R<ref>), [Y_4, Z] is complete. Then we see that by (R<ref>:a), G{v_1,v_3} is  a P_3-free expansion of a perfect graph, and hence perfect. This completes the proof of the theorem.






§ COLORING (P_5, PARAGLIDER)-FREE GRAPHS

Given a graph G and a proper homogeneous set X in G, let G/X
be the graph obtained by replacing X with a clique Q of size
ω(X) (i.e., G/X is obtained from G∖ X and Q by
adding all edges between Q and the vertices of V(G)∖ X
that are adjacent to X in G).
 The proof of the following lemma is very similar to that of Lemma 3.1  of <cit.> and we omit the details.


In a graph G let X be a proper homogeneous set such that G[X] is
perfect.  Then ω(G)=ω(G/X) and  χ(G)=χ(G/X).    


 Let C_5 be the class of
graphs that are P_3-free expansions of C_5, and let C_5^*
be the class of graphs that are clique expansions of C_5.

Let H^* be the class of graphs G ∈H such that, with the notation as in Section 1, the two sets R_1 and R_2 are cliques.

 Since  P_3-free graphs are perfect, the following lemma (Lemma <ref>) can be proved using Lemma <ref>, and the proof is very similar to that of Lemma 3.3  of <cit.>, so we omit the details.


 
For every graph G in C_5 (resp. G in H)
 there is a graph G^* in C_5^*
 (resp. G^* in H^*) such that
ω(G)=ω(G^*) and χ(G)=χ(G^*).




Let G be a clique expansion of C_5. Then  χ(G)≤⌈5ω(G)/4⌉.  


1cm
For any fixed integer k≥ 2, let G_k be the graph defined as follows.

=1pt

  * V(G_k) can be partitioned into three cliques Q_1:={a_1,a_2…, a_k}, Q_2:={b_1,b_2,…,b_k},
and S:={s_1,s_2,…,s_k} such that [Q_1, Q_2] is a perfect matching, say  {a_1b_1,a_2b_2,…,a_kb_k}.

  * There exists an injective function f:S→{1,2,…, k} such that for each vertex  x∈ S, {x} is anti-complete to {a_f(x), b_f(x)}, and is complete to (Q_1∪ Q_2) {a_f(x), b_f(x)}.

  * No other edges in G.



For each integer k≥ 2, χ(G_k)≤⌈3k/2⌉.



Without loss of generality, we may assume that for each i∈{1,2…,k},
s_i is anti-complete to {a_i,b_i} and complete to (Q_1∪ Q_2){a_i,b_i}.
We consider two cases depending on whether k is even or not.

Suppose first that k=2t for some t≥ 1. Now we color G_2t using 3t colors as follows:

∙ Color s_1,s_2,…,s_t with colors 1,2,…,t, respectively.

∙ Color s_t+1,s_t+2,…,s_2t with colors t+1,t+2,…,2t, respectively.

∙ Color a_1,a_2,…,a_t with colors 2t+1,2t+2,…,3t, respectively.

∙ Color a_t+1,a_t+2,…,a_2t with colors t+1,t+2,…,2t, respectively.

∙ Color b_1,b_2,…,b_t with colors 1,2,…,t, respectively.

∙ Color b_t+1,b_t+2,…,b_2t with colors 2t+1,2t+2,…,3t, respectively.

Then it can be easily checked that the above  is  a 3t-coloring of G_2t.

Next suppose that k=2t+1, for some t≥ 1. Then ⌈3k/2⌉=3t+2.
Observe that G_2t+1{s_2t+1,a_2t+1,b_2t+1} is isomorphic to G_2t.
Therefore, χ(G_2t+1)≤ 3t+2.



If G∈ℋ^*, χ(G)≤3ω(G)/2.



Let G be partitioned into Q_1, Q_2, R_1, R_2 and S.
Without loss of generality, we may assume that for each 1≤ i≤ |S|,
s_i is complete to (Q_1∪ Q_2)∖{a_i,b_i} and is anti-complete to {a_i,b_i}.
Let r=max{|R_1|,|R_2|}.
Since R_i∪ Q_i is a clique for i∈{1,2},
ω(G)≥ k+r.
Obviously,

    χ(G)≤χ(G[Q_1∪ Q_2∪ S])+χ(G[R_1∪ R_2]).

Since |S|≤ k, G[Q_1∪ Q_2∪ S] is an induced subgraph of G_k.
By Lemma <ref>, χ(G[Q_1∪ Q_2∪ S])≤⌈3k/2⌉.
On the other hand, since R_1 and R_2 are clique, χ(G[R_1∪ R_2])≤ r.
If r≥ 1, then r+1/2≤3r/2. Therefore,
χ(G)≤ (3k/2+1/2)+r≤3k/2+3r/2≤3ω(G)/2.
So we may assume that r=0.  Observe that ω(G)∈{k,k+1} and that if ω(G)= k, then |S|≤ k-2. If S=, then χ(G)≤ k ≤ω(G).
So, let S={s_1,s_2,…, s_t} for some 1≤ t≤ k.
Let

    G'     = G[{a_1,a_2,… a_t}∪{b_1,b_2,… b_t}∪{s_1,s_2,…,s_t}], 
    
    G”    = G[{a_t+1,…, a_k}∪{b_t+1,…, a_k}].


Observe that χ(G”)=k-t. Since G' is isomorphic to G_t, it follows from Lemma <ref> that
χ(G')≤⌈3t/2⌉≤3t/2+1/2. Therefore,
 χ(G)≤χ(G')+χ(G”)≤ (3t/2+1/2)+(k-t)=k+t/2+1/2. Now if ω(G)=k, then since t≤ k-2, we have χ(G)≤ k+k-2/2+1/2= 3k/2-1/2<3/2ω(G), and if ω(G)=k+1, then χ(G)≤ k+k/2+1/2< 3/2ω(G).



Let G be a graph and v∈ V(G). We say that G' is obtained from G by adding a smaller vertex u
if   N(u) is a non-empty subset of N(v) in G'. Let ℬ be the set of graphs that
consists of the complement of the Clebsch graph and the graph obtained from the complement of the Clebsch graph by deleting a vertex.
We note that any graph G∈ℬ has χ(G)=⌈3ω(G)/2⌉
and the ceiling is necessary. Moreover, it is not hard to verify that
these are the only induced subgraphs of the complement of the Clebsch graph that satisfy this property (This fact and Lemma <ref> below are verified by a computer program
due to Owen Merkel).
Let 𝒢 be the class of (P_5, paraglider)-free graphs that can be obtained from a graph in ℬ
by a sequence of adding a smaller vertex.  We say that a graph G is awesome if for every non-empty clique K of G, there exists
an induced P_4:= v-x-y-z such that v∈ K and x,y,z∉ K.
Then we have the following lemma and its proof is verified easily by a computer program.


Every graph G∈ℬ is awesome.





Every graph G∈𝒢 is awesome.




Let G∈𝒢. Then G is obtained from a graph B∈ℬ by adding smaller vertices u_1,…,u_k sequentially.
We prove the lemma by induction on k. If k=0, then the lemma holds by Lemma <ref>.
Suppose now that the lemma holds for all graphs in 𝒢 that are obtained from  a graph B∈ℬ by adding k-1 vertices
for some k≥ 1. Let G'=G-u_k. By the inductive hypothesis, G' is awesome, i.e., for every non-empty clique
K of G' there exists an induced P_4 := v-x-y-z such that v∈ K and x,y,z∉ K.

Now let K be a clique of G. If K∖{u_k} is non-empty, then it follows from the inductive hypothesis
that a desired P_4 exists for K. It remains to consider the case that K={u_k}, i.e., to show
that in G there is an induced P_4 := u_k-x-y-z.

Let v∈ V(G') be the vertex such that N_G(u_k)⊆ N_G(v).

Suppose first that N_G(u_k)=N_G(v). Since G' is awesome, there exists an induced path  v-x-y-z in G' (consider the clique {v}).
Thus, u_k-x-y-z is a desired P_4.

So, we may assume that there exists a vertex d∈ V(G') such that d is adjacent to v but not to u_k.
Suppose that u_k has two non-adjacent neighbors s and t in G. Since {v,s,u_k,t,d} does not induce a paraglider,
d is not adjacent to either s or t, say s. Then u_k-s-v-d is a desired P_4.

So, N_G(u_k) is a clique. Let w∈ V(G') be a neighbor of u. Since G' is awesome, there exists an induced P_4 := w-x-y-z in G'.
Since N_G(u_k) is a clique, u_k is adjacent to neither y nor z. If u_k is not adjacent to x, then u_k-w-x-y is a desired P_4.
Otherwise u is adjacent to x and u_k-x-y-z is a desired P_4.





We are now ready to prove the main theorem in this section.


Let G be a connected (P_5, paraglider)-free graph. Then χ(G)≤⌈3ω(G)/2⌉.
Moreover, χ(G)>3ω(G)/2 if and only if G∈𝒢.



Observe that every graph H in 𝒢 has χ(H)=8 and ω(H)=5 and so χ(H)=⌈3ω(H)/2⌉.
Therefore, if G∈𝒢 then χ(G)>3ω(G)/2.
We now show by induction on |V(G)| that if  G∉𝒢, then χ(G)≤3ω(G)/2.
This will imply the theorem.

First, suppose that G contains a pair of comparable vertices u and v, say N(u)⊆ N(v).
Then since G∉𝒢, it follows that G-u∉𝒢.
Moreover, G-u is connected. By the inductive hypothesis,
χ(G-u)≤3ω(G-u)/2. Note that χ(G)=χ(G-u) and ω(G)=ω(G-u).
Therefore, χ(G)≤3ω(G)/2.

Suppose now that G contains a clique cutset. Let K be a minimal clique cutset and G K is the disjoint union of two
subgraphs H_1 and H_2. Let G_i=G[K∪ V(H_i)] for i∈{1,2}. Note that G_1 and G_2 are connected.
We show that  neither G_1 nor G_2 is in 𝒢.
Suppose not. We may assume by symmetry that G_1∈𝒢.
Since K is a non-empty clique of G_1, it follows from Lemma <ref>
that there exists an induced P_4 := v-x-y-z with v∈ K and x,y,z∉ K.
Since K is minimal, v has a neighbor w in G_2. Then w-v-x-y-z is a P_5.
This contradicts the fact that G is P_5-free.
Since neither G_1 nor G_2 is in 𝒢, χ(G_i)≤3ω(G_i)/2 by the inductive hypothesis.
Therefore, χ(G)=max{χ(G_1),χ(G_2)}≤3ω(G)/2.

Suppose that G contains a universal vertex u. If G-u is disconnected, then {u} is a clique cutset of G and we are done by the argument on clique cutsets. Therefore, G-u is connected.
If G-u∉𝒢, then
it follows from the inductive hypothesis that
χ(G-u)≤3ω(G-u)/2+1=3(ω(G)-1)/2+1<3ω(G)/2.
If G-u∈𝒢, then since every graph in 𝒢 has clique number 5 and chromatic number 8,
it follows that χ(G)=9 and ω(G)=6. Thus, χ(G)=3ω(G)/2.


Therefore, we may assume that G contains no clique cutsets, universal vertices or pairs of comparable vertices.
We now can apply the structure theorem.

If G is an induced subgraph of the complement of the Clebsch graph,
then the theorem clearly holds.

If G is a P_3-free expansion of C_5, then it follows by Lemma <ref> that χ(G)≤⌈5ω(G)/4⌉≤3ω(G)/2.

Suppose that G has a good stable set S, and that H_1,…,H_t are the component of G S, where t≥ 1.
Since S is good,  it follows that ω(H_i)≤ω(G)-1.
We claim that χ(H_i)≤3/2ω(G)-1 for each i∈{1,…,t}.
If H_i∉𝒢,  then it follow from the inductive hypothesis that
χ(H_i)≤3ω(H_i)/2≤3(ω(G)-1)/2< 3ω(G)/2-1.
If H_i∈𝒢, then ω(H_i)=5 and  χ(H_i)=8. This implies that ω(G)≥ 6.
Thus, χ(H_i)=8=3/2× 6-1≤3/2ω(G)-1.
Therefore, χ(G)≤max_1≤ i≤ tχ(H_i)+1≤3/2ω(G).

If G has a stable set S such that S is perfect,
then χ(G)≤χ(G S)+1=ω(G S)+1≤ω(G)+1≤3ω(G)/2.

If G∈ℋ, then the theorem follows from Lemma <ref> and Theorem <ref>.


The following construction shows that
our bound in Theorem <ref> is tight up to an additive constant.
Consider the graph G_k, for k≥ 2 as defined earlier.  Note that G_k∈H.
It is not hard to verify that G is (P_5, paraglider)-free, α(G_k)=2,
and  ω(G_k)=k+1. Since χ(G_k)≥|V(G_k)|/α(G_k),
we have χ(G_k)≥3k/2=3/2(ω(G_k)-1).
When k=2t+1 for some integer t≥ 1, it follows from Lemma <ref>
that χ(G_k)=3t+2=⌈3ω(G_k)/2⌉ -1.
This implies that there is no (3/2-ϵ)-approximation algorithm for the chromatic number for (P_5, paraglider)-free graphs
for any ϵ>0.

Theorem <ref> has the following two corollaries.


Every (P_5, paraglider)-free graph G has χ(G)≤⌈3ω(G)/2⌉.



Let G_1,…,G_t with t≥ 1 be the components of G. Then by Theorem <ref>,
χ(G_i)≤⌈3ω(G_i)/2⌉≤⌈3ω(G)/2⌉.
Since χ(G)=max_1≤ i≤ tχ(G_i), the corollary follows.



Let G be a (P_5, paraglider)-free graph (not necessarily connected). Then χ(G)>3ω(G)/2 if and only if
there exists a component C of G such that C∈𝒢 and ω(G)≤ 5.



Clearly, if G has a component C of G such that C∈𝒢 and ω(G)≤ 5, then
χ(G)=8 and ω(G)=5 and so χ(G)>3ω(G)/2.

Conversely, suppose that G does not satisfy the condition. We show that χ(G)≤3ω(G)/2.
Let G_1,…,G_t with t≥ 1 be the components of G. If none of G_1,…,G_t is in 𝒢,
then by Theorem <ref>, χ(G_i)≤3ω(G_i)/2≤3ω(G)/2 and so we are done.
So we may assume by symmetry that G_1∈𝒢. Then ω(G)≥ 6.
For each 1≤ i≤ t, we show that χ(G_i)≤3ω(G)/2.
If G_i∈𝒢, then χ(G_i)=8=3/2× 6-1≤3/2ω(G)-1.
If G_i∉𝒢,  then χ(G_i)≤3ω(G)/2 by Theorem <ref>.
This completes the proof.


Acknowledgment. We would like to thank Owen Merkel for writing a computer program to verify that
the complement of the Clebsch graph and
the graph obtained from the complement of the Clebsch graph by deleting a vertex are the only two induced subgraphs
of the complement of the Clebsch graph that satisfy χ=⌈3ω/2⌉ where the ceiling is necessary,
and Lemma <ref>.






99

BH
A. Brandstädt and C. T. Hoàng.  On clique separators, nearly chordal
graphs, and the maximum weight stable set problem.  Theoretical
Computer  Science 389 (2007) 295–306.



BRSVC. Brause, B. Randerath, I. Schiermeyer and E. Vumar. On the chromatic number of 2K_2-free graphs. Discrete Applied Mathematics. 253 (2019) 14–24.

CKS
S. A. Choudum, T. Karthick, M. A. Shalu.   Perfect coloring and
linearly χ-bounded P_6-free graphs.  Journal of Graph
Theory 54 (2007) 293–306.

CKS-2
S. A. Choudum, T. Karthick, M. A. Shalu. Linear chromatic bounds for a
subfamily of 3K_1-free graphs. Graphs and Combinatorics 24 (2008) 413–428.

Chud-surveyM. Chudnovsky, The Erdös–Hajnal conjecture–a survey. Journal of Graph Theory 75 (2014) 178–190.

CKMM M. Chudnovsky, T. Karthick, P. Maceli and F. Maffray, Coloring graphs with no induced five-vertex path or gem. Available on: arXiv:1810.06186 [math.CO].



Chud-Siva M. Chudnovsky and V. Sivaraman. Perfect divisibility and 2-divisibility. Journal of
Graph Theory 90 (2019) 54–60.

SPGTM. Chudnovsky, P. Seymour, N. Robertson and R. Thomas. The strong perfect
graph theorem. Annals of Mathematics 164 (2006) 51–229.

Fouquet
J. L. Fouquet, V. Giakoumakis, F. Maire and H. Thuillier.  On graphs
without P_5 and P_5.  Discrete Mathematics
146, 33–44 (1995).

KM2018
T. Karthick and F. Maffray,  Coloring (gem, co-gem)-free graphs.  Journal of Graph Theory 89 (2018) 288–303.

KMT. Karthick and F. Maffray. Vizing bound for the chromatic number on some graph classes.
Graphs and Combinatorics 32 (2016) 1447–1460.

KP
H. A. Kierstead and S. G. Penrice.  Radius two trees specify χ-bounded
classes.  Journal of Graph Theory 18 (1994) 119–129.


KPT-P5
H. A. Kierstead, S. G. Penrice and W. T. Trotter, On-line and first-fit
coloring of graphs that do not induce P_5.  SIAM Journal of
Discrete Mathematics 8 (1995) 485–498.


KZ
H. A. Kierstead and Y. Zhu.  Radius three trees in graphs with large
chromatic number.  SIAM Journal of Discrete Mathematics 17
(2004) 571–581.

LovaszL. Lovász, A characterization of perfect
graphs. Journal of Combinatorial Theory, Series B 13 (1972) 95–98.


















Gyarfas
A. Gyárfás. Problems from the world surrounding perfect
graphs.  Zastosowania Matematyki Applicationes Mathematicae 19
(1987) 413–441.

SS
A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic
number.  I. Odd holes.  Journal of Combinatorial Theory, Series  B 121
(2016) 68–-84.

surveyI. Schiermeyer and B. Randerath, Polynomial χ-binding functions and forbidden induced
subgraphs: A Survey. Graphs and Combinatorics 35 (2019) 1–35.











