On the Chromatic Number of (P₅, C₅, Cricket)-Free Graphs

Weilun Xu

School of Mathematics and Statistics, Shandong Normal University, Jinan, China.

DOI: 10.4236/eng.2022.143014                

Abstract

For a graph G, let be the chromatic number of G. It is well-known that holds for any graph G with clique number . For a hereditary graph class , whether there exists a function f such that holds for every has been widely studied. Moreover, the form of minimum such an f is also concerned. A result of Schiermeyer shows that every -free graph G with clique number has . Chudnovsky and Sivaraman proved that every -free with clique number graph is -colorable. In this paper, for any -free graph G with clique number , we prove that . The main methods in the proof are set partition and induction.

Keywords

P₅-Free Graphs, Chromatic Number, X-Boundedness

1. Introduction

In this paper, we consider undirected, simple graphs. For a given graph H, a graph G is called H-free if G contains no induced subgraphs isomorphic to H. Let $H_1\mathrm{,}{H}_2\mathrm{,}\cdots \mathrm{,}{H}_k$ $\left(k\ge 2\right)$ be different graphs. If for any $1\le i\le k$, G is $H_i$ -free, then we say that G is $\left(H_1\mathrm{,}{H}_2\mathrm{,}\cdots \mathrm{,}{H}_k\right)$ -free. A graph $G=\left(V\mathrm{,}E\right)$ is k-colorable if there exists a function $\phi \mathrm{<mo>\; :\; </mo>}V\left(G\right)\mapsto \left\{\mathrm{1,2,}\cdots \mathrm{,}k\right\}$ such that for any $uv\in E\left(G\right)$, there is $\phi \left(u\right)\ne \phi \left(v\right)$. The chromatic number of G is the minimum integer k such that G is k-colorable, denoted by $\chi \left(G\right)$. For a graph $G=\left(V\mathrm{,}E\right)$, a subset S of $V\left(G\right)$ is called a clique if S induces a complete subgraph. We use $\omega \left(G\right)$ to denote the maximum size of cliques of G. It is well-known that $\omega \left(G\right)\le \chi \left(G\right)$ for every graph G. A graph is perfect if for any induced subgraph $G^{\prime }$ of G, $\omega \left(G^{\prime }\right)=\chi \left(G^{\prime }\right)$. Chudnovsky et al. [1] gave an equivalent characterization of perfect graphs, which is also called as the Strong Perfect Graph Theorem.

Theorem 1.1. [1] A graph is perfect if and only if it contains neither odd cycles of length at least five nor the complements of these odd cycles.

We say a hereditary graph class $G$ is $\chi$ -bounded, if there exists a function f such that for any $G\in G$, $\chi \left(G\right)\le f\left(\omega \left(G\right)\right)$. Moreover, f is called a $\chi$ -binding function of $G$. Erdös [2] showed that for arbitrary integers $k\mathrm{,}l\ge 3$, there exists a graph G with girth at least l and $\chi \left(G\right)\ge k$, which implies that the class of H-free graphs is not $\chi$ -bounded when H contains a cycle. Gyárfás conjectured that the graph class obtained by forbidding a tree (or forest) is $\chi$ -bounded.

Conjecture 1.2. [3] Let T be a tree (or forest), then there exists a function $f_T$ such that, for any T-free graph G, $\chi \left(G\right)\le f_T\left(\omega \left(G\right)\right)$ .

Moreover, Gyárfás [3] verified this conjecture when $T=P_k$, and showed that $f_T\le {\left(k-1\right)}^{\omega \left(G\right)-1}$. When $T=P_5$, Esperet et al. [4] gave a $\chi$ -binding function of $P_5$ -free graphs as following.

Theorem 1.3. [4] Suppose G is a $P_5$ -free graph with clique number $\omega \ge 3$ . Then $\chi \left(G\right)\le 5\cdot 3^{\omega -3}$ .

As far as we know, for $\omega \ge 3$, $f\left(\omega \right)=5\cdot 3^{\omega -3}$ is the optimal $\chi$ -binding function of $P_5$ -free graphs at present. Furthermore, determining a polynomial $\chi$ -binding function of the class of $P_5$ -free graphs is an open problem. A result in [5] shows that the class of H-free graphs has a linear $\chi$ -binding function f, if and only if $f\left(\omega \right)=\omega$ and H is an induced subgraph of $P_4$, which means that the class of $P_5$ -free graphs has no linear $\chi$ -binding function.

In this paper, we focus on subclasses of $P_5$ -free graphs. While the class of $P_5$ -free graphs has no linear $\chi$ -binding function, some subclasses of $P_5$ -free have linear $\chi$ -binding functions.

Theorem 1.4. [6] [7] [8] [9] Suppose $H\in \left\{diamond\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>}gem\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>}paraglider\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>}paw\right\}$ , then the class of $\left(P_5\mathrm{,}H\right)$ -free graphs has a $\chi$ -binding function.

More formally, Chudnovsky et al. [6] proved that the class of $\left(P_5\mathrm{,}\text{gem}\right)$ -free graphs has a $\chi$ -binding function $f\left(\omega \right)\le \lceil \frac{5}{4}\omega \rceil$. Huang and Karthick [7] showed that $\left(P_5\mathrm{,}\text{paraglider}\right)$ graphs have a $\chi$ -binding function $f\left(\omega \right)\le \lceil \frac{3}{2}\omega \rceil$. Karthick and Maffray [8] gave a $\chi$ -binding function $f\left(\omega \right)=\omega +1$ for $\left(P_5\mathrm{,}\text{diamond}\right)$ -free graphs. And Randerath [9] showed that $\left(P_5\mathrm{,}\text{paw}\right)$ -free graphs have a $\chi$ -binding function $f\left(\omega \right)=\omega +1$ (diamond, gem, paraglider and paw are given in Figure 1).

It is worth noting that a result in [10] shows that when H contains an independent set with size at least 3, the class of $\left(P_5\mathrm{,}H\right)$ -free graphs has no linear $\chi$ -binding function.

Figure 1. Examples of diamond, gem, paraglider and paw.

Theorem 1.5. [10] The class of $\left(2K_2\mathrm{,3}{K}_1\right)$ -free graphs has no linear $\chi$ -binding function.

Obviously, when H is a graph with independent number at least 3, $\left(P_5\mathrm{,}H\right)$ -free graphs is a superclass of $\left(2K_2\mathrm{,3}{K}_1\right)$ -free graphs. Thus the class of $\left(P_5\mathrm{,}H\right)$ -free graphs has no $\chi$ -binding function.

The following theorem shows that some subclasses of $P_5$ -free graphs have a $\chi$ -binding function $f\left(\omega \right)=\left(\begin{array}{c}\omega +1\\ 2\end{array}\right)$ (The addition forbidden subgraphs are given in Figure 2).

Theorem 1.6. [10] [11] [12] The class of $\left(P_5\mathrm{,}H\right)$ -free graphs has a $\chi$ -binding function $f\left(\omega \right)=\left(\begin{array}{c}\omega +1\\ 2\end{array}\right)$ when $H\in \left\{bull\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>}house\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>}hammer\right\}$ .

In [13], Schiermeyer proved that the class of $\left(P_5\mathrm{,}H\right)$ -free graphs has a $\chi$ -binding function $f\left(\omega \right)={\omega }^2$ for $H\in \left\{\text{claw}\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>}\text{cricket}\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>}\text{dart}\mathrm{,\; <mtext>\; \hspace{0.17em}\; </mtext>}\text{gem}+\right\}$ (see Figure 3).

In addition to the subclasses of $P_5$ -free graphs we mentioned above, there are many subclasses had been proved that admit a polynomial $\chi$ -binding function, which is given in [14] and [15]. More results on $\chi$ -binding function, see [16].

The class of $\left(P_5\mathrm{,}{C}_5\right)$ -free graphs, which is a superclass of $\left(P_5\mathrm{,}{C}_5\mathrm{,}\text{cricket}\right)$ -free graphs, has been studied by Chudnovsky and Sivaraman [11]. They showed that every $\left(P_5\mathrm{,}{C}_5\right)$ -free graph with clique number $\omega$ is $2^{\omega -1}$ -colorable. In this paper, we obtain the following result. In the next section, we will give the proof.

Theorem 1.7. Every $\left(P_5\mathrm{,}{C}_5\mathrm{,}\text{cricket}\right)$ -free graph G with clique number $\omega$ has $\chi \left(G\right)\le \lceil \frac{{\omega }^2}{2}\rceil +\omega$ .

2. The Proof of Main Result

For two vertex sets A and B, let $E\left(A\mathrm{,}B\right)=\left\{uv\in E\left(G\right)\mathrm{<mo>\; :\; </mo>}u\in A\text{and}v\in B\right\}$. We say that A is complete to B, if for any $x\in A$ and $y\in B$, $xy\in E\left(G\right)$. For a given graph $G=\left(V\mathrm{,}E\right)$, let $N\left(v\right)$ denote the neighborhood of $v\in V\left(G\right)$, and for a subset S of $V\left(G\right)$, set $N\left(S\right)={\displaystyle {\cup }_{v\in S}}N\left(v\right)$. An induced subgraph D of G is called a dominating D, if there is $V\left(G\right)\backslash V\left(D\right)\subseteq N\left(V\left(D\right)\right)$. In this paper, for an induced $P_4$ : $P=v_1{v}_2{v}_3{v}_4$, we simply write $V\left(P\right)$ as P. First, we give a lemma based on the structure of a $\left(P_5\mathrm{,}{C}_5\right)$ -free graph.

Figure 2. Examples of bull, hammer and house.

Figure 3. Examples of claw, cricket, dart and gem+.

Lemma 2.1. If $P=v_1{v}_2{v}_3{v}_4$ is a dominating $P_4$ of a $\left(P_5\mathrm{,}{C}_5\right)$ -free graph G, then $v_2{v}_3$ is a dominating edge of G.

Suppose, to the contrary, that there exists a vertex $u\notin N\left(v_2\right)\cup N\left(v_3\right)$. Since P is a dominating $P_4$, $u\in N\left(v_1\right)\cup N\left(v_4\right)$. By symmetry, we may assume that $u{v}_1\in E\left(G\right)$. If $u{v}_4\in E\left(G\right)$, then $u{v}_1{v}_2{v}_3{v}_{4}u$ would be an induced $C_5$. If $u{v}_4\notin E\left(G\right)$, then $u{v}_1{v}_2{v}_3{v}_4$ would be an induced $P_5$. Either deduces a contradiction.

Next, we show that a subclass of $\left(P_5\mathrm{,}{C}_5\mathrm{,}\text{cricket}\right)$ -free graphs has a $\chi$ -binding function $f\left(\omega \right)=\lceil \frac{{\omega }^2}{2}\rceil$. Let $i{K}_1+K_2$ be the graph consisted of one edge and i isolated vertices.

Lemma 2.2. Every $\left(P_5\mathrm{,}{C}_5\mathrm{,2}{K}_1+K_2\right)$ -free graph G with clique number $\omega$ has $\chi \left(G\right)\le \lceil \frac{{\omega }^2}{2}\rceil$ .

Apply induction on $\omega$. If $\omega =1$, it is obviously true. When $\omega =2$, it is also true because every $\left(P_5\mathrm{,}{C}_5\mathrm{,}{K}_3\right)$ -free graph is a bipartite graph. Moreover, when $\omega =3$, by Theorem 1.3, $\chi \left(G\right)\le 5=\lceil \frac{9}{2}\rceil$. Next, consider the cases $\omega \ge 4$. If G is $P_4$ -free, then G is perfect by Theorem 1.1. So we may suppose that $P=v_1{v}_2{v}_3{v}_4$ is an induced $P_4$. We claim that P is a dominating $P_4$ of G. Otherwise, there would exist a vertex $u\in V\left(G\right)\backslash N\left(P\right)$. Noting that $P\subseteq N\left(P\right)$, $\left\{u\mathrm{,}{v}_1\mathrm{,}{v}_3\mathrm{,}{v}_4\right\}$ induces a $2K_1+K_2$, a contradiction. By Lemma 2.1, $v_2{v}_3$ is a dominating edge of G. Next, denote

$V_2=\left\{v\mathrm{<mo>\; :\; </mo>}v{v}_2\in E\left(G\right)\text{and}v{v}_3\notin E\left(G\right)\right\}\backslash \left\{v_3\right\}\mathrm{,}$

$V_3=\left\{v\mathrm{<mo>\; :\; </mo>}v{v}_2\notin E\left(G\right)\text{and}v{v}_3\in E\left(G\right)\right\}\backslash \left\{v_2\right\}\mathrm{,}$

$V_{\mathrm{2,3}}=N\left(v_2\right)\cap N\left(v_3\right)\mathrm{.}$

For clarity, we give this partition in Figure 4. Let $G\left[S\right]$ denote the subgraph of G induced by S. Clearly, $G\left[V_2\right]$ is $\left(P_5\mathrm{,}{C}_5\mathrm{,}{K}_1+K_2\right)$ -free. (Otherwise, let $\left\{u_1\mathrm{,}{u}_2\mathrm{,}{u}_3\right\}$ be an induced $K_1+K_2$ of $G\left[V_2\right]$. Then $\left\{u_1\mathrm{,}{u}_2\mathrm{,}{u}_3\mathrm{,}{v}_3\right\}$ would induce a $2K_1+K_2$.) By Theorem 1.1, $G\left[V_2\right]$ is perfect. Noting that $\omega \left(G\left[V_2\right]\right)\le \omega -1$, we have $\chi \left(G\left[V_2\right]\right)\le \omega -1$. Similarly, $\chi \left(G\left[V_3\right]\right)\le \omega -1$. Moreover, there is $\omega \left(G\left[V_{\mathrm{2,3}}\right]\right)\le \omega -2$. By induction, $\chi \left(G\left[V_{\mathrm{2,3}}\right]\right)\le \lceil \frac{{\left(\omega -2\right)}^2}{2}\rceil$.

Now we color G. Let $K=\left\{\mathrm{1,2,}\cdots \mathrm{,}\lceil \frac{{\omega }^2}{2}\rceil \right\}$ be a color set. First, we color $v_2$ and $v_3$ by colors 1 and 2, respectively. Noting that $E\left(V_2\mathrm{,}\left\{v_3\right\}\right)=\varnothing$, $V_2$ can be colored by $\left\{\mathrm{2,3,}\cdots \mathrm{,}\omega \right\}$. Similarly, $V_3$ can be colored by $\left\{\mathrm{1,}\omega +\mathrm{1,}\cdots \mathrm{,2}\omega -2\right\}$. Thus, $\chi \left(G\left[V_2\cup V_3\cup \left\{v_2\mathrm{,}{v}_3\right\}\right]\right)\le 2\omega -2$. Since $v_2{v}_3$ is a dominating edge of G, $V\left(G\right)=\left\{v_2\mathrm{,}{v}_3\right\}\cup V_2\cup V_3\cup V_{\mathrm{2,3}}$. So we have

$\chi \left(G\right)\le \chi \left(G\left[V_2\cup V_3\cup \left\{v_2\mathrm{,}{v}_3\right\}\right]\right)+\chi \left(G\left[V_{\mathrm{2,3}}\right]\right)\le 2\omega -2+\lceil \frac{{\left(\omega -2\right)}^2}{2}\rceil =\lceil \frac{{\omega }^2}{2}\rceil \mathrm{.}$

Note that the bound given by Lemma 2.2 is tight for $\omega =2$, and $C_4$ is a $\left(P_5\mathrm{,}{C}_5\mathrm{,}\text{cricket}\right)$ -free graph with clique number 2 and chromatic number 2.

Proof of Theorem 1.7

When $\omega \le 3$, it is obviously true. Next, assume that $\omega \ge 4$. If G is $P_4$ -free, then $\chi \left(G\right)=\omega$ by Theorem 1.1. So we may suppose that $P=v_1{v}_2{v}_3{v}_4$ is an induced $P_4$ of G. Let $N_2\left(P\right)=N\left(N\left(P\right)\right)\backslash N\left(P\right)$ and $N_3\left(P\right)=N\left(N_2\left(P\right)\right)\backslash N\left(P\right)$. Moreover, for arbitrary different $i\mathrm{,}j\mathrm{,}k\in \left\{\mathrm{1,2,3,4}\right\}$, denote

$U_i=\left\{v\in N\left(P\right)\backslash P:N\left(v\right)\cap P=\left\{v_i\right\}\right\},$

$U_{i,j}=\left\{v\in N\left(P\right)\backslash P:N\left(v\right)\cap P=\left\{v_i,v_j\right\}\right\},$

$U_{i,j,k}=\left\{v\in N\left(P\right)\backslash P:N\left(v\right)\cap P=\left\{v_i,v_j,v_k\right\}\right\},$

$A=\left\{v\in N\left(P\right)\backslash P:N\left(v\right)\cap P=P\right\}.$

Figure 4. A partition of $V\left(G\right)$.

Clearly, $U_{i,j}=U_{j,i}$ and $U_{i,k,j}=U_{i,j,k}=U_{j,i,k}$. Since G is $\left(P_5\mathrm{,}{C}_5\right)$ -free, $U_1=U_4=U_{1,4}=\varnothing$. So

$A\cup U_2\cup U_3\cup U_{1,2}\cup U_{1,3}\cup U_{2,3}\cup U_{2,4}\cup U_{3,4}\cup U_{1,2,3}\cup U_{1,2,4}\cup U_{1,3,4}\cup U_{2,3,4}=N\left(P\right)\backslash P$.

The partition is shown in Figure 5. Since G is $P_5$ -free, there is no vertex with a distance of 4 to P. So we can partition $V\left(G\right)$ into $N\left(P\right)$, $N_2\left(P\right)$, $N_3\left(P\right)$, and color these sets respectively. Next, we give two claims based on $N_3\left(P\right)$ and $N_2\left(P\right)$.

Claim 1 $N_3\left(P\right)=\varnothing$.

Otherwise, suppose there are vertices $x_3\in N_3\left(P\right)$ and $x_2\in N_2\left(P\right)$ such that $x_2{x}_3\in E\left(G\right)$. Let $u\in N\left(P\right)\backslash P$ be a neighbor of $x_2$. If $u\in A$, then $\left\{x_2\mathrm{,}u\mathrm{,}{v}_1\mathrm{,}{v}_2\mathrm{,}{v}_4\right\}$ would induce a cricket, a contradiction. So there exists $v_i$ and $v_j$ ( $i\mathrm{,}j\in \left\{\mathrm{1,2,3,4}\right\}$ ) such that $v_i{v}_j\in E\left(G\right)$, $u{v}_i\in E\left(G\right)$ and $u{v}_j\notin E\left(G\right)$. Now $x_3{x}_{2}u{v}_i{v}_j$ is an induced $P_5$, a contradiction.

Claim 2 Let T be a connected component of $G\left[N_2\left(P\right)\right]$ with $\left|V\left(T\right)\right|\ge 2$ , then then at least one vertex of $U_{\mathrm{2,3}}$ is complete to $V\left(T\right)$ .

First, we show that every edge $xy$ in T has $N\left(x\right)\cap N\left(P\right)=N\left(y\right)\cap N\left(P\right)$. Suppose, to the contrary, that there exists a vertex $u\in \left(N\left(x\right)\cap N\left(P\right)\right)\backslash \left(N\left(y\right)\cap N\left(P\right)\right)$. Similar to the proof of Claim 1, there is an induced cricket or induced $P_5$, a contradiction. So, for each $xy\in E\left(T\right)$, x and y have same neighborhood in $N\left(P\right)$. By connectivity and transitivity, all vertices in T have same neighborhood in $N\left(P\right)$. Then there is at least one vertex, say u, in $N\left(P\right)\backslash P$ such that $V\left(T\right)$ is complete to $\left\{u\right\}$.

Next, we pick an arbitrary edge $xy$ in T. Then $xuy$ is a triangle. If $u\in U_2\cup U_{\mathrm{1,2}}$, then $xu{v}_2{v}_3{v}_4$ would be an induced $P_5$. And if $u\in A\cup U_{\mathrm{1,3}}\cup U_{\mathrm{1,2,3}}\cup U_{\mathrm{1,3,4}}$, then $\left\{x\mathrm{,}y\mathrm{,}u\mathrm{,}{v}_1\mathrm{,}{v}_3\right\}$ would induce a cricket. Up to symmetry, there must be $u\in U_{\mathrm{2,3}}$.

By Claim 2, for an arbitrary connected component T of $G\left[N_2\left(P\right)\right]$, there exists a vertex $u\in U_{\mathrm{2,3}}$ such that $\left\{u\right\}$ is complete to $V\left(T\right)$. If there exists $x\mathrm{,}y\in V\left(T\right)$ such that $xy\notin E\left(G\right)$, then $\left\{x\mathrm{,}y\mathrm{,}u\mathrm{,}{v}_2\mathrm{,}{v}_3\right\}$ would induce a cricket. Thus $V\left(T\right)$ is a clique with size at most $\omega -1$, which implies that

$\chi \left(G\left[N_2\left(P\right)\right]\right)\le \omega -1.$ (1)

Let $G^{\prime }=G\left[N\left(P\right)\right]$. Note that P is a dominating $P_4$ of $G^{\prime }$. By Lemma 2.1, $v_2{v}_3$ is a dominating edge of $G^{\prime }$. Thus $V\left(G^{\prime }\right)\backslash \left\{v_2\mathrm{,}{v}_3\right\}$ can be partitioned into $\left\{V_2\mathrm{,}{V}_3\mathrm{,}{V}_{\mathrm{2,3}}\right\}$, which is defined as in Lemma 2.2. Since $G^{\prime }$ is $\left(P_5\mathrm{,}{C}_5\mathrm{,}\text{cricket}\right)$ -free, both $G\left[V_2\right]$ and $G\left[V_3\right]$ are $\left(P_5\mathrm{,}{C}_5\mathrm{,}{K}_1+K_2\right)$ -free. Thus, by the coloring described in Lemma 2.2, there is

$\chi \left(G\left[V_2\cup V_3\cup \left\{v_2\mathrm{,}{v}_3\right\}\right]\right)\le 2\omega -2$. Moreover, noting that $G\left[V_{\mathrm{2,3}}\right]$ is complete to $\left\{v_2\mathrm{,}{v}_3\right\}$, we have that $G\left[V_{\mathrm{2,3}}\right]$ is $\left(P_5\mathrm{,}{C}_5\mathrm{,2}{K}_1+K_2\right)$ -free and $\omega \left(G\left[V_{\mathrm{2,3}}\right]\right)\le \omega -2$. By Lemma 2.2, $\chi \left(G\left[V_{\mathrm{2,3}}\right]\right)\le \lceil \frac{{\left(\omega -2\right)}^2}{2}\rceil$. Thus,

Figure 5. A partition of $N\left(P\right)\backslash P$.

$\chi \left(G^{\prime }\right)\le \chi \left(G\left[V_2\cup V_3\cup \left\{v_2,v_3\right\}\right]\right)+\chi \left(G\left[V_{2,3}\right]\right)\le 2\omega -2+\lceil \frac{{\left(\omega -2\right)}^2}{2}\rceil \le \lceil \frac{{\omega }^2}{2}\rceil .$ (2)

By Claim 1, $V\left(G\right)=N\left(P\right)\cup N_2\left(P\right)$. Hence, by Inequality (1) and (2), there is

$\chi \left(G\right)\le \chi \left(G^{\prime }\right)+\chi \left(G\left[N_2\left(P\right)\right]\right)\le \lceil \frac{{\omega }^2}{2}\rceil +\omega \mathrm{.}$

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Chudnovsky, M., Robertson, N., Seymour, P. and Thomas, R. (2006) The Strong Perfect Graph Theorem. Annals of Mathematic, 164, 51-229. https://doi.org/10.4007/annals.2006.164.51
[2]	Erdös, P. (1959) Graph Theory and Probability. Classic Papers in Combinatorics, 11, 34-38. https://doi.org/10.4153/CJM-1959-003-9
[3]	Gyárfás, A. (1987) Problems from the World Surrounding Perfect Graphs. Applicationes Mathematicae, 19, 413-441. https://doi.org/10.4064/am-19-3-4-413-441
[4]	Esperet, L., Lemoine, L., Maffray, F. and Morel, G. (2013) The Chromatic Number of (P5, K4)-Free Graphs. Discrete Mathematics, 313, 743-754. https://doi.org/10.1016/j.disc.2012.12.019
[5]	Randerath, B. and Schiermeyer, I. (2004) Vertex Colouring and Forbidden Subgraphs—A Survey. Graphs and Combinatorics, 20, 1-40. https://doi.org/10.1007/s00373-003-0540-1
[6]	Chudnovsky, M., Karthick, T., Maceli, P. and Maffray, F. (2020) Coloring Graphs with No Induced Five-Vertex Path or Gem. Journal of Graph Theory, 95, 527-542. https://doi.org/10.1002/jgt.22572
[7]	Huang, S. and Karthick, T. (2021) On Graphs with No Induced Five-Vertex Path or Paraglider. Journal of Graph Theory, 97, 305-323. https://doi.org/10.1002/jgt.22656
[8]	Karthick, T. and Maffray, F. (2016) Vizing Bound for the Chromatic Number on Some Graph Classes. Graphs and Combinatorics, 32, 1447-1460. https://doi.org/10.1007/s00373-015-1651-1
[9]	Randerath, B. (1998) The Vizing Bound for the Chromatic Number Based on Forbidden Pairs. Ph.D. Thesis, RWTH Aachen, Shaker Verlag.
[10]	Brause, C., Randerath, B., Schiermeyer, I. and Vumar, E. (2019) On the Chromatic Number of 2K2-Free Graphs. Discrete Applied Mathematics, 253, 14-24. https://doi.org/10.1016/j.dam.2018.09.030
[11]	Chudnovsky, M. and Sivaraman, V. (2019) Perfect Divisibility and 2-Divisibility. Journal of Graph Theory, 90, 54-60. https://doi.org/10.1002/jgt.22367
[12]	Fouquet, J., Giakoumakis, V., Maire, F. and Thuillier, H. (1995) On Graphs without P5 and P5. Discrete Mathematics, 146, 33-44. https://doi.org/10.1016/0012-365X(94)00155-X
[13]	Schiermeyer, I. (2016) Chromatic Number of P5-Free Graphs: Reed’s Conjecture. Discrete Mathematics, 339, 1940-1943. https://doi.org/10.1016/j.disc.2015.11.020
[14]	Brause, C., Doan, T. and Schiermeyer, I. (2016) On the Chromatic Number of (P5, K2,t)-Free Graphs. Electronic Notes in Discrete Mathematics, 55, 127-130. https://doi.org/10.1016/j.endm.2016.10.032
[15]	Schiermeyer, I. (2017) On the Chromatic Number of (P5, Windmill)-Free Graphs. Opuscula Mathematica, 37, 609-615. https://doi.org/10.7494/OpMath.2017.37.4.609
[16]	Schiermeyer, I. and Randerath, B. (2019) Polynomial X-Binding Functions and Forbidden Induced Subgraphs: A Survey. Graphs and Combinatorics, 35, 1-31. https://doi.org/10.1007/s00373-018-1999-0