Chromatic Bounds for Some Subclasses of $(P_3\cup P_2)$-free graphs

Abstract

The class of $2K_2$-free graphs has been well studied in various contexts in the past. It is known that the class of $\{2K_2,2K_1+K_p\}$-free graphs and $\{2K_2,(K_1\cup K_2)+K_p\}$-free graphs admits a linear $\chi$-binding function. In this paper, we study the classes of $(P_3\cup P_2)$-free graphs which is a superclass of $2K_2$-free graphs. We show that $\{P_3\cup P_2,2K_1+K_p\}$-free graphs and $\{P_3\cup P_2,(K_1\cup K_2)+K_p\}$-free graphs also admits a linear $\chi$-binding function. In addition, we give tight chromatic bounds for $\{P_3\cup P_2,HVN\}$-free graphs and $\{P_3\cup P_2,diamond\}$-free graphs, and it can be seen that the latter is an improvement of the existing bound given by A. P. Bharathi and S. A. Choudum [1].

1 Introduction

All graphs considered in this paper are simple, finite and undirected. Let G be a graph with vertex set V(G) and edge set E(G). For any positive integer k, a proper k-coloring of a graph G is a mapping c : $V(G)\rightarrow \{1,2,\ldots ,k\}$ such that adjacent vertices receive distinct colors. If a graph G admits a proper k-coloring, then G is said to be k-colorable. The chromatic number, $\chi (G)$, of a graph G is the smallest k such that G is k-colorable. Let $P_n, C_n$ and $K_n$ respectively denote the path, the cycle and the complete graph on n vertices. For $S,T\subseteq V(G)$, let $N_T(S) = N(S)\cap T$ (where N(S) denotes the set of all neighbors of S in G), let $\langle S\rangle$ denote the subgraph induced by S in G and let [S, T] denote the set of all edges with one end in S and the other end in T. If every vertex in S is adjacent with every vertex in T, then [S, T] is said to be complete. For any graph G, let $\overline{G}$ denote the complement of G.

Let $\mathcal {F}$ be a family of graphs. We say that G is $\mathcal {F}$-free if it does not contain any induced subgraph which is isomorphic to a graph in $\mathcal {F}$. For a fixed graph H, let us denote the family of H-free graphs by $\mathcal {G}(H)$. For any two disjoint graphs $G_1$ and $G_2$ let $G_1\cup G_2$ and $G_1+G_2$ denote the union and the join of $G_1$ and $G_2$ respectively. Let $\omega (G)$ and $\alpha (G)$ denote the clique number and independence number of a graph G respectively. When there is no ambiguity, $\omega (G)$ will be denoted by $\omega$. A graph G is said to be perfect if $\chi (H)=\omega (H)$, for every induced subgraph H of G.

In order to determine an upper bound for the chromatic number of a graph in terms of their clique number, the concept of $\chi$-binding functions was introduced by A. Gyárfás in [4]. A class $\mathcal {G}$ of graphs is said to be $\chi$-bounded [4] if there is a function f (called a $\chi$-binding function) such that $\chi (G)\le f(\omega (G))$, for every $G\in \mathcal {G}$. We say that the $\chi$-binding function f is special linear if $f(x)= x+c$, where c is a constant.

The family of $2K_2$-free graphs has been well studied. A. Gyárfás in [4] posed a problem which asks for the order of magnitude of the smallest $\chi$-binding function for $\mathcal {G}(2K_2)$. In this direction, T. Karthick et al. in [5] proved that the families of $\{2K_2, H\}$-free graphs, where $H\in \{HVN, diamond, K_1+P_4, K_1 + C_4, \overline{P_5}, \overline{P_2 \cup P_3}, K_5-e\}$ admit a special linear $\chi$-binding functions. The bounds for $\{2K_2,K_5-e\}$-free graphs and $\{2K_2,K_1+C_4\}$-free graphs were later improved by Athmakoori Prashant et al., in [7, 8]. In [2], C. Brause et al., improved the $\chi$-binding function for $\{2K_2,K_1+P_4\}$-free graphs to $\max \{3, \omega (G)\}$. Also they proved that for $s\ne 1$ or $\omega (G)\ne 2$, the class of $\{2K_2, (K_1\cup K_2)+K_s\}$-free graphs with $\omega (G)\ge 2s$ is perfect and for $r\ge 1$, the class of $\{2K_2, 2K_1+K_r\}$-free graphs with $\omega (G)\ge 2r$ is perfect. Clearly when $s=2$ and $r=3$, $(K_1\cup K_2)+K_s\cong HVN$ and $2K_1+K_r\cong K_5-e$ which implies that the class of $\{2K_2,HVN\}$-free graphs and $\{2K_2,K_5-e\}$-free graphs are perfect for $\omega (G)\ge 4$ and $\omega (G)\ge 6$ respectively which improved the bounds given in [5].

Motivated by C. Brause et al., and their work on $2K_2$-free graphs in [2], we started looking at $(P_3\cup P_2)$-free graphs which is a superclass of $2K_2$-free graphs. In [1], A. P. Bharathi et al., obtained a $O(\omega ^3)$ upper bound for the chromatic number of $(P_3\cup P_2)$-free graphs and obtained sharper bounds for $\{P_3\cup P_2,diamond\})$-free graphs. In this paper, we obtain linear $\chi$-binding functions for the class of $\{P_3\cup P_2, (K_1\cup K_2)+K_p\}$-free graphs and $\{P_3\cup P_2, 2K_1+K_p\}$-free graphs. In addition, for $\omega (G)\ge 3p-1$, we show that the class of $\{P_3\cup P_2, (K_1\cup K_2)+K_p\}$-free graphs admits a special linear $\chi$-binding function $f(x)=\omega (G) +p-1$ and the class of $\{P_3\cup P_2, 2K_1+K_p\}$-free graphs are perfect. In addition, we give a tight $\chi$-binding function for $\{P_3\cup P_2,HVN\}$-free graphs and $\{P_3\cup P_2,diamond\}$-free graphs. This bound for $\{P_3\cup P_2, diamond\}$-free graphs turns out to be an improvement of the existing bound obtained by A. P. Bharathi et al., in [1].

Fig. 1.

Some special graphs

Some graphs that are considered as forbidden induced subgraphs in this paper are given in Fig. 1. Notations and terminologies not mentioned here are as in [10].

2 Preliminaries

Throughout this paper, we use a particular partition of the vertex set of a graph G as defined initially by S. Wagon in [9] and later improved by A. P. Bharathi et al., in [1] as follows. Let $A=\{v_1,v_2,\ldots ,v_{\omega }\}$ be a maximum clique of G. Let us define the lexicographic ordering on the set $L=\{(i, j): 1 \le i < j \le \omega \}$ in the following way. For two distinct elements $(i_1,j_1),(i_2,j_2)\in L$, we say that $(i_1,j_1)$ precedes $(i_2,j_2)$, denoted by $(i_1,j_1)<_L(i_2,j_2)$ if either $i_1<i_2$ or $i_1=i_2$ and $j_1<j_2$. For every $(i,j)\in L$, let $C_{i,j}=\left\{ v\in V(G)\backslash A:v\notin N(v_i)\cup N(v_j)\right\} \backslash \left\{ \mathop \cup \limits _{(i',j')<_L(i,j)} C_{i',j'}\right\}$. Note that, for any $k\in \{1,2,\ldots ,j\}\backslash \{i,j\}$, $[v_k,C_{i,j}]$ is complete. Hence $\omega (\langle C_{i,j}\rangle )\le \omega (G)-j+2$.

For $1\le k\le \omega$, let us define $I_k=\{v\in V(G)\backslash A: v\in N(v_i), \text { for every }\ i\in \{1,2,\ldots ,\omega \}\backslash \{k\}\}$. Since A is a maximum clique, for $1\le k\le \omega$, $I_k$ is an independent set and for any $x\in I_k$, $xv_k\notin E(G)$. Clearly, each vertex in $V(G)\backslash A$ is non-adjacent to at least one vertex in A. Hence those vertices will be contained either in $I_k$ for some $k\in \{1,2,\ldots ,\omega \}$, or in $C_{i,j}$ for some $(i,j)\in L$. Thus $V(G)=A\cup \left( \mathop \cup \limits _{k=1}^{\omega }I_k\right) \cup \left( \mathop \cup \limits _{(i,j)\in L}C_{i,j}\right)$. Sometimes, we use the partition $V(G)=V_1\cup V_2$, where $V_1=\mathop \cup \limits _{1\le k\le \omega }(\{v_k\}\cup I_k)=\mathop \cup \limits _{1\le k\le \omega }U_k$ and $V_2=\mathop \cup \limits _{(i,j)\in L}C_{i,j}$.

Let us recall a result on $\left( P_3\cup P_2\right)$-free graphs given by A. P. Bharathi et al., in [1].

Theorem 1

[1]. If a graph G is $(P_3\cup P_2)$-free, then $\chi (G)\le \frac{\omega (G)\left( \omega (G)+1\right) \left( \omega (G)+2\right) }{6}$.

Without much difficulty one can make the following observations on $\left( P_3\cup P_2\right)$-free graphs.

Fact 2

Let G be a $\left( P_3\cup P_2\right)$-free graph. For $(i,j)\in L$, the following holds.

• (i) Each $C_{i,j}$ is a disjoint union of cliques, that is, $\langle C_{i,j}\rangle$ is $P_3$-free.

• (ii) For every integer $s\in \{1,2,\ldots ,j\}\backslash \{i,j\}$, $N(v_s)\supseteq \{C_{i,j}\cup A\cup (\mathop \cup \limits _{k=1}^{\omega }I_k)\}\backslash \{v_s\cup I_s\}$.

3 $\{P_3\cup P_2, (K_1\cup K_2)+K_p\}$-free graphs

Let us start Sect. 3 with some observations on $((K_1\cup K_2)+K_p)$-free graphs.

Proposition 1

Let G be a $((K_1\cup K_2)+K_p)$-free graph with $\omega (G)\ge p+2$, $p\ge 1$. Then G satisfies the following.

• (i) For $k,\ell \in \{1,2,\ldots ,\omega (G)\}$, $[I_k,I_{\ell }]$ is complete. Thus, $\langle V_1\rangle$ is a complete multipartite graph with $U_{k}=\{v_{k}\}\cup I_{k}$, $1\le k\le \omega (G)$ as its partitions.

• (ii) For $j\ge p+2$ and $1\le i<j$, $C_{i,j}=\emptyset$.

• (iii) For $x\in V_2$, x has neighbors in at most $(p-1)$ $U_\ell$’s where $\ell \in \{1,2,\ldots ,\omega (G)\}$.

Proposition 2

Let G be a $\{P_3\cup P_2,(K_1\cup K_2)+K_p\}$-free graph with $\omega (G)\ge p+2$, $p\ge 1$. Then G satisfies the following.

• (i) For $(i,j)\in L$ such that $j\le p+1$, if $\omega (\langle C_{i,j}\rangle )\ge p-j+4$, then $\omega (\langle C_{k,j}\rangle )\le 1$ for $k\ne i$ and $1\le k \le j-1$.

• (ii) If $\omega (G)=(p+2+k)$, $k\ge 0$, then $\left\langle \left( \mathop \cup \limits _{j=\max \{2,p+1-\lfloor \frac{k}{2}\rfloor \}}^{p+1} \left( \mathop \cup \limits _{i=1}^{j-1} C_{i,j}\right) \right) \right\rangle$ is $P_3$-free.

As a consequence of Proposition 1, we obtain Corollary 1 which is a result due to S. Olariu in [6].

Corollary 1

[6]. Let G be a connected graph. Then G is paw-free graph if and only if G is either $K_3$-free or complete multipartite.

Now, for $p\ge 1$ and $\omega \ge \max \{3,3p-1\}$, let us determine the structural characterization and the chromatic number of $\{P_3\cup P_2,(K_1\cup K_2)+K_p\}$-free graphs.

Theorem 3

Let p be a positive integer and G be a $\{P_3\cup P_2, (K_1\cup K_2)+K_p\}$-free graph with $V(G)=V_1\cup V_2$. If $\omega (G)\ge \max \{3,3p-1\}$, then (i) $\langle V_1\rangle$ is a complete multipartite graph with partition $U_1,U_2, \ldots , U_{\omega }$, (ii) $\langle V_2\rangle$ is $P_3$-free graph and (iii) $\chi (G)\le \omega (G)+p-1$.

Proof

Let $p\ge 1$ and G be a $\{P_3\cup P_2, (K_1\cup K_2)+K_p\}$-free graph with $\omega (G)\ge \max \{3,3p-1\}$. By (i) of Proposition 1, we see that $\langle V_1\rangle$ is a complete multipartite graph with the partition $U_{k}=\{v_{k}\}\cup I_{k}$, $1\le k\le \omega$. By (i) of Fact 2, each $\langle C_{i,j}\rangle$ is $P_3$-free, for every $(i,j)\in L$. Also without much difficulty we can show that $\left\langle V_2\right\rangle$ is $P_3$-free. Now, let us exhibit an $(\omega +p-1)$-coloring for G using $\{1,2,\ldots , \omega +p-1\}$ colors. For $1\le k \le \omega$, give the color k to the vertices of $U_k$. Let H be a component in $\left\langle V_2\right\rangle$. Clearly, each vertex in H is adjacent to at most $p-1$ colors given to the vertices of $V_1$ and is adjacent to $\omega (H)-1$ vertices of H. Since $\omega (H)\le \omega (G)$, each vertex in H is adjacent to at most $\omega (G)+p-2$ colors. Hence, there is a color available for each vertex in H. Similarly, all the components of $\left\langle V_2\right\rangle$ can be colored properly. Hence, $\chi (G)\le \omega (G)+p-1$.

Even though we are not able to show that the bound given in Theorem 3 is tight, we can observe that the upper bound cannot be made smaller than $\omega +\lceil \frac{p-1}{2}\rceil$ by providing the following example. For $p\ge 1$, consider the graph $G^*$ with $V(G^*)=X\,\cup \,Y\,\cup \,Z$, where $X= \mathop {\cup }\limits _{i=1}^\omega x_i$, $Y= \mathop \cup \limits _{i=1}^{\omega }y_i$ and $Z=\mathop \cup \limits _{i=1}^{p-1}z_i$ if $p\ge 2$ else $Z=\emptyset$ and edge set $E(G^*)=\{\{x_ix_j\}\cup \{y_iy_j\}\cup \{z_rz_s\}\cup \{x_my_n\}\cup \{y_mz_n\}\cup \{ x_nz_n\}$, where $1\le i,j,m\le \omega$, $1\le r,s,n\le p-1$, $i\ne j$, $r\ne s$ and $m\ne n$}. Without much difficulty, one can observe that $G^*$ is a $\{P_3\cup P_2,(K_1 \cup K_2)+K_p\}$-free graph, $\omega (G^*)=\omega$ and $\alpha (G^*)=2$. Hence, $\chi (G^*)\ge \left\lceil \frac{|V(G^*)|}{\alpha (G^*)}\right\rceil =\omega (G^*)+\left\lceil \frac{p-1}{2}\right\rceil$.

Next, we obtain a linear $\chi$-binding function for $\{P_3\cup P_2, (K_1\cup K_2)+K_p\}$-free graphs with $\omega \ge 3$.

Theorem 4

Let p be an integer greater than 1. If G is a $\{P_3\cup P_2, (K_1\cup K_2)+K_p\}$-free graph, then

$$\begin{aligned} \chi (G)\le \left\{ \begin{array}{lcl} \omega (G)+\sum \limits _{j=2}^{p+1} (j-1)(p-j+3) &{} \text {for} &{} 3\le \omega (G)\le p+1\\ \omega (G)+7(p-1)+\sum \limits _{j=4}^{p-\left\lfloor \frac{k}{2}\right\rfloor } (j-1)(p-j+3) &{} \text {for} &{} \omega (G)= (p+2+k), 0\le k\le 2p-5 \\ \omega (G)+4p-3 &{} \text {for} &{} \omega (G)= 3p-2\\ \omega (G)+p-1 &{} \text {for} &{} \omega (G)\ge 3p-1. \end{array} \right. \end{aligned}$$

Proof

Let G be a $\{P_3\cup P_2, (K_1\cup K_2)+K_p\}$-free graph with $p\ge 2$. For $\omega (G)\ge 3p-1$, the bound follows from Theorem 3. By (ii) of Proposition 1, we see that $C_{i,j}=\emptyset$ for all $j\ge p+2$. We know that $V(G)=V_1\cup V_2$, where $V_1=\mathop \cup \limits _{1\le \ell \le \omega }(\{v_{\ell }\}\cup I_{\ell })$ and $V_2=\mathop \cup \limits _{(i,j)\in L}C_{i,j}$. Clearly, the vertices of $V_1$ can be colored with $\omega (G)$ colors. Let us find an upper bound for $\chi (\langle V_2\rangle )$. First, let us consider the case when $3\le \omega (G)\le p+1$. For $1\le i< j\le p+1$, one can observe that $\omega (\langle C_{i,j}\rangle )\le \omega (G)-j+2\le p-j+3$. Thus one can properly color the vertices of $\left( \mathop \cup \limits _{i=1}^{j-1} C_{i,j}\right)$ with at most $(j-1)(p-j+3)$ colors and hence $\chi (G) \le \chi (\langle V_1\rangle )+\chi (\langle V_2\rangle )\le \omega (G)+\sum \limits _{j=2}^{p+1} (j-1)(p-j+3)$.

Next, let us consider $\omega (G) = (p+2+k)$, where $0\le k\le 2p-4$. By using (ii) of Proposition 2, $\left\langle \left( \mathop \cup \limits _{j=p-\lfloor \frac{k}{2}\rfloor +1}^{p+1} \left( \mathop \cup \limits _{i=1}^{j-1} C_{i,j}\right) \right) \right\rangle$ is a $P_3$-free graph. As in Theorem 3, one can color the vertices of $V(G)\backslash \left\{ \mathop \cup \limits _{j=2}^{p-\lfloor \frac{k}{2}\rfloor } \left( \mathop \cup \limits _{i=1}^{j-1} C_{i,j}\right) \right\}$ with at most $\omega (G)+p-1$ colors. For $k=2p-4$, $\omega (G)=3p-2$ and we see that $\langle V_2\backslash C_{1,2}\rangle$ is $P_3$-free and $\chi (\langle V(G)\backslash C_{1,2}\rangle )\le \omega (G)+p-1$. Therefore, $\chi (G)\le \chi (\langle V(G)\backslash C_{1,2}\rangle )+\chi (\langle C_{1,2}\rangle )=\omega (G)+4p-3$. Finally, for $0\le k\le 2p-5$, by using (i) of Proposition 2 and by using similar strategies but with a little more involvement, we can show that $\left( \mathop \cup \limits _{i=1}^{j-1} C_{i,j}\right)$, where $2\le j\le p-\lfloor \frac{k}{2}\rfloor$ can be properly colored using $\omega (G)$ colors when $\omega (\langle C_{i,j}\rangle )\ge p-j+4$, for some $i\in \{1,2,\ldots ,j-1\}$ or by using $(j-1)(p-j+3)$ colors when $\omega (\langle C_{i,j}\rangle )\le p-j+3$, for every $i\in \{1,2,\ldots ,j-1\}$. For $4\le j\le p-\left\lfloor \frac{k}{2}\right\rfloor$, one can observe that $(j-1)(p-j+3)\ge \omega (G)$ and hence the vertices of $\left( \mathop \cup \limits _{j=4}^{p-\lfloor \frac{k}{2}\rfloor } \left( \mathop \cup \limits _{i=1}^{j-1} C_{i,j}\right) \right)$ can be properly colored with $\sum \limits _{j=4}^{p-\lfloor \frac{k}{2}\rfloor } (j-1)(p-j+3)$ colors. When $j=3$, $(j-1)(p-j+3)=2p$. Since $2p-5\ge 0$, $p\ge 3$. Also, since $\omega (G)\ge 4$, the vertices of $C_{1,2}$ and $(C_{1,3}\cup C_{2,3})$ can be properly colored with at most $(3p-3)$ colors each. Hence, $\chi (G) \le (\omega (G)+p-1)+2(3p-3)+\sum \limits _{j=4}^{p-\lfloor \frac{k}{2}\rfloor } (j-1)(p-j+3)=\omega (G)+7(p-1)+\sum \limits _{j=4}^{p-\lfloor \frac{k}{2}\rfloor } (j-1)(p-j+3)$.

The bound obtained in Theorem 4 is not optimal. This can be seen in Theorem 5. Note that when $p=2$, $(K_1\cup K_2)+K_p\cong HVN$.

Theorem 5

If G is a $\{P_3\cup P_2, HVN\}$-free graph with $\omega (G)\ge 4$, then $\chi (G)\le \omega (G)+1$.

The graph $G^*$ (defined next to Theorem 3) shows that the bound given in Theorem 5 is tight.

4 $\{P_3\cup P_2, 2K_1+K_p\}$-free graphs

Let us start Sect. 4 by observing that any $\{P_3\cup P_2, 2K_1+K_p\}$-free graph is also a $\{P_3\cup P_2, (K_1\cup K_2)+K_p\}$-free graph. Hence the properties established for $\{P_3\cup P_2, (K_1\cup K_2)+K_p\}$-free graphs is also true for $\{P_3\cup P_2, 2K_1+K_p\}$-free graphs.

One can observe that by using techniques similar to the one’s used in Theorem 3 and by Strong Perfect Graph Theorem [3], any $\{P_3\cup P_2,2K_1+K_p\}$-free graph is perfect, when $\omega \ge 3p-1$.

Theorem 6

Let p be a positive integer and G be a $\{P_3\cup P_2, 2K_1+K_p\}$-free graph with $V(G)=V_1\cup V_2$. If $\omega (G)\ge 3p-1$, then $\langle V_1\rangle$ is complete, $\langle V_2\rangle$ is $P_3$-free and G is perfect.

As a consequence of Theorem 4 and Theorem 6, without much difficulty one can observe Proposition 3 and Corollary 2.

Proposition 3

Let G be a $\{P_3\cup P_2, 2K_1+K_p\}$-free graph. If $\omega (\langle C_{1,2}\rangle )\ge 2p$, then $\chi (G)=\omega (G)$.

Corollary 2

Let p be an integer greater than 1. If G is a $\{P_3\cup P_2, 2K_1+K_p\}$-free graph, then

$$\begin{aligned} \chi (G)\le \left\{ \begin{array}{lcl} \omega (G)+\sum \limits _{j=2}^{p+1} (j-1)(p-j+3) &{} \text {for} &{} 3\le \omega (G)\le p+1\\ \omega (G)+2p-1+\sum \limits _{j=3}^{p-\left\lfloor \frac{k}{2}\right\rfloor } (j-1)(p-j+3) &{} \text {for} &{} \omega (G)= (p+2+k), 0\le k\le 2p-5 \\ \omega (G)+2p-1 &{} \text {for} &{} \omega (G)= 3p-2\\ \omega (G) &{} \text {for} &{} \omega (G)\ge 3p-1. \end{array} \right. \end{aligned}$$

When $p=2$, $2K_1+K_p\cong diamond$ and hence by Theorem 6, $\{P_3\cup P_2, diamond\}$-free graphs are perfect for $\omega (G)\ge 5$ which was shown by A. P. Bharathi et al., in [1].

Theorem 7

[1]. If G is a $\{P_3\cup P_2, diamond\}$-free graph then $\chi (G)\le \left\{ \begin{array}{lcl} 4 &{} \text {for} &{} \omega (G)= 2\\ 6 &{} \text {for} &{} \omega (G)= 3\\ 5 &{} \text {for} &{} \omega (G)= 4\\ \end{array} \right.$ and G is perfect if $\omega (G)\ge 5$.

We can further improve the bound given in Theorem 7 by obtaining a $\omega (G)$-coloring when $\omega (G)=4$.

Theorem 8

If G is a $\{P_3\cup P_2, diamond\}$-free graph then $\chi (G)\le \left\{ \begin{array}{lcl} 4 &{} \text {for} &{} \omega (G)= 2\\ 6 &{} \text {for} &{} \omega (G)= 3\\ 4 &{} \text {for} &{} \omega (G)=4. \end{array} \right.$ and G is perfect if $\omega (G)\ge 5$.