On the Chromatic Number of (*P*_{5}, *C*_{5}, Cricket)-Free Graphs ()

Weilun Xu^{}

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

**DOI: **10.4236/eng.2022.143014
PDF
HTML XML
105
Downloads
627
Views
Citations

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

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

Share and Cite:

Xu, W. (2022) On the Chromatic Number of (*P*_{5}, *C*_{5}, Cricket)-Free Graphs. *Engineering*, **14**, 147-154. doi: 10.4236/eng.2022.143014.

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{:}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{,\text{\hspace{0.17em}}}gem\mathrm{,\text{\hspace{0.17em}}}paraglider\mathrm{,\text{\hspace{0.17em}}}paw\right\}$ *,* then the class of
$\left({P}_{5}\mathrm{,}H\right)$ -free graphs ha**s** 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(2{K}_{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(2{K}_{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{,\text{\hspace{0.17em}}}house\mathrm{,\text{\hspace{0.17em}}}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{,\text{\hspace{0.17em}}}\text{cricket}\mathrm{,\text{\hspace{0.17em}}}\text{dart}\mathrm{,\text{\hspace{0.17em}}}\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{:}u\in A\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}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}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}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
$2{K}_{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{:}v{v}_{2}\in E\left(G\right)\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}v{v}_{3}\notin E\left(G\right)\right\}\backslash \left\{{v}_{3}\right\}\mathrm{,}$

${V}_{3}=\left\{v\mathrm{:}v{v}_{2}\notin E\left(G\right)\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}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
$2{K}_{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.

[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 |

Journals Menu

Contact us

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2023 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.