More Results on Clique-chromatic Numbers of Graphs with No Long Path

Abstract

The clique-chromatic number of a graph is the least number of colors on the vertices of the graph so that no maximal clique of size at least two is monochromatic. In 2003, Gravier, Hoang, and Maffray have shown that, for any graph $F$, the class of $F$-free graphs has a bounded clique-chromatic number if and only if $F$ is a vertex-disjoint union of paths, and they give an upper bound for all such cases. In this paper, their bounds for $F=P_2+kP_1$ and $F=P_3+kP_1$ with $k \ge 3$ are significantly reduced to $k+1$ and $k+2$ respectively, and sharp bounds are given for some subclasses.

Tanawat Wichianpaisarn—Partially supported by His Royal Highness Crown Prince Maha Vajiralongkorn Fund.

1 Introduction

All graphs considered in this paper are simple. We use terminologies from West’s textbook [9]. $V(G)$ and $E(G)$ denote the vertex set and the edge set of a graph $G$, respectively. The symbols $K_n$, $P_n$ and $C_n$ denote the complete graph, path, and cycle, with $n$ vertices, respectively. The diamond is the complete graph $K_4$ minus an edge. The neighborhood of a vertex $x$ in a graph $G$ is the set of vertices adjacent to $x$, and is denoted by $N_{G}(x)$. For $S \subseteq V(G)$, $N_{S}(x)$ stands for the neighborhood of a vertex $x$ in $S$, that is, $N_{S}(x) = N_G(x) \cap S$. Given graphs $G_1,G_2,\ldots ,G_k$ with pairwise disjoint vertex sets, the disjoint union of graphs $G_1,G_2,\ldots ,G_k$ is the graph with vertex set $\bigcup _{i=1}^{k}V(G_i)$ and edge set $\bigcup _{i=1}^{k}E(G_i)$, denoted by $G_1 + G_2 + \cdots + G_k$. For $k \in \mathbb {N}$, $kG$ is the disjoint union of $k$ pairwise disjoint copies of a graph $G$.

A subset $Q$ of $V(G)$ is a clique of $G$ if any two vertices of $Q$ are adjacent. A clique is maximal if it is not properly contained in another clique. A k-coloring of a graph $G$ is a function $f : V(G)\rightarrow \{1,2,\ldots ,k\}$. A proper k-coloring of a graph $G$ is a $k$-coloring of $G$ such that adjacent vertices have different colors. The chromatic number of a graph $G$ is the smallest positive integer $k$ such that $G$ has a proper $k$-coloring, denoted by $\chi (G)$. A proper k-clique-coloring of a graph $G$ is a $k$-coloring of $G$ such that no maximal clique of $G$ with size at least two is monochromatic. A graph $G$ is k-clique-colorable if $G$ has a proper $k$-clique-coloring. The clique-chromatic number of $G$ is the smallest $k$ such that $G$ has a proper $k$-clique-coloring, denoted by $\chi _{c}(G)$. Note that $\chi _{c}(G) = 1$ if and only if $G$ is an edgeless graph. Since any proper $k$-coloring of $G$ is a proper $k$-clique-coloring of $G$, $\chi _{c}(G) \le \chi (G)$. Recall that a triangle is the complete graph $K_3$. If $G$ is a triangle-free graph, then maximal cliques of $G$ are edges; so $\chi _{c}(G) = \chi (G)$. Mycielski [8] showed that the family of triangle-free graphs has no bounded chromatic number. Consequently, it has no bounded clique-chromatic number, either. On the other hand, many families of graphs have bounded clique-chromatic numbers, for example, comparability graphs, cocomparability graphs, and the $k$-power of cycles (see [2, 4, 5]). In 2004, Bacso et al. [1] proved that almost all perfect graphs are 3-clique-colorable and conjectured that all perfect graphs are 3-clique-colorable.

A subgraph $H$ of a graph $G$ is said to be $induced$ if, for any pair of vertices $x$ and $y$ of $H$, $xy$ is an edge of $H$ if and only if $xy$ is an edge of $G$. For a given graph $F$, a graph $G$ is F-free if it does not contain $F$ as an induced subgraph. A graph $G$ is $(F_1,F_2,\ldots ,F_k)$ -free if it is $F_i$-free for all $1 \le i \le k$. In [6], Gravier, Hoang and Maffray gave a significant result that, for any graph $F$, the family of all $F$-free graphs has a bounded clique-chromatic number if and only if $F$ is a vertex-disjoint union of paths. Many authors explored more results in $(F_1,F_2,\ldots ,F_k)$-free graphs. Gravier and Skrekovski [7] in 2003 proved that $(P_3+P_1)$-free graphs unless it is $C_5$, and $(P_5,C_5)$-free graphs are 2-clique-colorable. In 2004, Bacso et al. [1] showed that (claw, odd hole)-free graphs are 2-clique-colorable. Later, Defossez [3] in 2006 proved that (diamond, odd hole)-free graphs are 4-clique-colorable, and (bull, odd hole)-free graphs are 2-clique-colorable.

Given a graph $F$, let $f(F) = \max \{\chi _{c}(G)~|~G$ is an $F$-free graph}. When $F_1$ is an induced subgraph of $F_2$, if a graph $G$ is $F_1$-free then $G$ is also $F_2$-free, it follows that $f(F_1) \le f(F_2)$. In 2003, Gravier, Hoang and Maffray [6] showed the following result.

Theorem 1

[6]. Let F be a graph. Then $f(F)$ exists if and only if $F$ is a vertex-disjoint union of paths. Moreover,

• if $|V(F)| \le 2$ or F = ${P_3}$ then $f(F) \le 2$,

• else $f(F)\le cc(F)+|V(F)|-3$ where $cc(F)$ is the number of connected components of a graph $F$.

Furthermore, they proved that $(P_2+2P_1)$-free graphs and $(P_3+2P_1)$-free graphs are 3-clique-colorable. Since the cycle $C_5$ is both $(P_2+2P_1)$-free and $(P_3+2P_1)$-free with $\chi _c(C_5) = 3$, this bound is sharp.

2 Main Results

An independent set in a graph is a set of pairwise nonadjacent vertices. A maximum independent set of a graph $G$ is a largest independent set of $G$ and its size is denoted by $\alpha (G)$. Bacso et al. [1] stated the relationship between the clique-chromatic number and the size of a maximum independent set of a graph, as follows.

Theorem 2

[1]. Let $G$ be a graph. If $G \ne C_5$ and G is not a complete graph, then $\chi _{c}(G) \le \alpha (G)$.

It follows from Theorem 1 that every $(P_2+kP_1)$-free graph is ($2k$)-clique-colorable and every $(P_3+kP_1)$-free graph is ($2k+1$)-clique-colorable. We improve these upper bounds for $k \ge 3$.

Theorem 3

For $k \ge 3$, a $(P_2+kP_1)$-free graph is $(k+1)$-clique-colorable.

Proof

Let $G$ be a $(P_2+kP_1)$-free graph. Let $S = \{s_0,s_1,\ldots ,s_{\alpha (G)-1}\}$ be a maximum independent set of $G$. If $\alpha (G) \le k$, then $\chi _{c}(G) \le k$ by Theorem 2.

Assume $\alpha (G) \ge k+1$. Let $M(s_0) = V(G) {\setminus } (S \cup N_G(s_0))$. For $R \subseteq S {\setminus } \{s_0\}$, define $Y_{R} = \{v \in M(s_0) ~|~ N_S(v) = S {\setminus } (\{s_0\} \cup R)\}$ and $\min (R) = \min \{i \in \mathbb {N}~|~s_i \notin R\}$. In particular, $\min (\emptyset ) = 1$. Note that $V(G)$ is the disjoint union of $S,~N_G(s_0)$ and $Y_{R}$ where $R \subseteq S {\setminus } \{s_0\}$. Let $f$ be the coloring of $G$ defined by

$$ f(v) = {\left\{ \begin{array}{ll} 1, &{}\text {if} ~~ v \in S \\ 2, &{}\text {if} ~~ v \in N_G(s_0) \\ \min (R)+2, &{}\text {if} ~~ v \in Y_{R} ~\text {where}~ R = S {\setminus } (\{s_0\} \cup N_S(v)). \end{array}\right. } $$

Now, let $R \subseteq S {\setminus } \{s_0\}$ where $Y_R \ne \emptyset$, and let $y \in Y_R$. If $R = S {\setminus } \{s_0\}$, then $N_S(y) = \emptyset$; so $S \cup \{y\}$ is an independent set of $G$. This contradicts the maximality of $S$. Thus $R \ne S {\setminus } \{s_0\}$. If $|R| \ge k-1$, then the subgraph of $G$ induced by $S \cup \{y\}$ contains an induced subgraph $P_2+kP_1$, a contradiction. Thus $|R| \le k-2$, and it follows that $\min (R) \le k-1$. Therefore, $f$ is a ($k+1$)-coloring of $G$. Suppose that $G$ has a monocolored maximal clique $Q$ of size at least two, say colored by $m$. Since $S$ is an independent set, $m \ne 1$. Thus $Q \cap S = \emptyset$. Note that $s_{\min (R)}$ is adjacent to all vertices of $Y_R$. Thus $s_{m-2}$ is adjacent to all vertices of $Q$. Then $Q \cup \{s_{m-2}\}$ is a clique of $G$. It contradicts the maximality of $Q$. Hence $\chi _{c}(G) \le k+1$.

Theorem 4

For $k \ge 3$, a $(P_3+kP_1)$-free graph is $(k+2)$-clique-colorable.

Proof

Let $G$ be a $(P_3+kP_1)$-free graph. Let $S = \{s_1,s_2,\ldots ,s_{\alpha (G)}\}$ be a maximum independent set of $G$. If $\alpha (G) \le k+1$, then $\chi _{c}(G) \le k+1$ by Theorem 2. Assume $\alpha (G) \ge k+2$. For $1 \le i \le \alpha (G)$, let $X_i = \{v \in V(G) {\setminus } S ~|~ N_S(v) = \{s_i\} \}$. Suppose that there is an edge, say $x_ix_j$, between $X_i$ and $X_j$ where $i \ne j$. Then there exist $k$ vertices in $S {\setminus } \{s_i,s_j\}$ together with $s_i,x_i,x_j$ form an induced subgraph $P_3+kP_1$ of $G$, a contradiction. Thus there is no edge between any two $X_i$’s. For $R \subseteq S$ where $|R| \ne \alpha (G)-1$, define $Y_{R} = \{v \in V(G) {\setminus } S ~|~ N_S(v) = S {\setminus } R\}$ and $\min (R) = \min \{i \in \mathbb {N}~|~s_i \notin R\}$. Note that $V(G)$ is the disjoint union of $S,~X_i$ where $1 \le i \le \alpha (G)$, and $Y_{R}$ where $R \subseteq S$ and $|R| \ne \alpha (G)-1$. Let $f$ be the coloring of $G$ defined by

$$ f(v) = {\left\{ \begin{array}{ll} 1, &{}\text {if} ~~~ v \in S \\ 2, &{}\text {if} ~~~ v \in \mathop {\bigcup }\nolimits _{i=1}^{\alpha (G)}X_i \\ \min (R)+2, &{}\text {if} ~~~ v \in Y_{R} ~\text {where}~ R = S {\setminus } N_S(v). \end{array}\right. } $$

Let $R \subseteq S$ where $Y_R \ne \emptyset$, and let $y \in Y_R$. If $R = S$, then $N_S(y) = \emptyset$ ; so $S \cup \{y\}$ is an independent set of $G$, a contradiction. If $k \le |R| \le \alpha (G)-2$, then the subgraph of $G$ induced by $S \cup \{y\}$ contains an induced subgraph $P_3+kP_1$, a contradiction. Thus $|R| \le k-1$, and it follows that $\min (R) \le k$. Hence $f$ is a ($k+2$)-coloring of $G$. Now, suppose that $G$ has a monocolored maximal clique $Q$ of size at least two, say colored by $m$. Since $S$ is an independent set, $m \ne 1$. If $m$ = 2, then $Q \subseteq X_i$ for some $i$. We have that $s_i$ is adjacent to all vertices of $Q$, a contradiction. Now, assume $m \ge 3$. Since $s_{\min (R)}$ is adjacent to all vertices of $Y_R$, $s_{m-2}$ is adjacent to all vertices of $Q$, a contradiction. Thus $f$ is a proper $(k+2)$-clique-coloring of $G$, and hence $\chi _{c}(G) \le k+2$.

Theorem 3 ensures that every $(P_2+kP_1)$-free graph where $k \ge 3$ is ($k+1$)-clique-colorable but we have found no graph guaranteeing this sharpness yet. However, when $k$ = 3 and 4, there is a $(P_2+kP_1)$-free graph which is $k$-clique-colorable, namely, the cycle $C_5$ is $(P_2+3P_1)$-free and $\chi _{c}(C_5) = 3$, and the 4-chromatic Mycielski’s graph $G_4$ [8] is ($P_2+4P_1$)-free and $\chi _{c}(G_4) = 4$. (See Fig. 1) Notice that both of them are diamond-free, this suggests the result in Theorem 5.

Fig. 1.

The 4-chromatic Mycielski’s graph $G_4$

Theorem 5

For $k \ge 3$, a $(P_2+kP_1$, diamond$)$-free graph is $k$-clique-colorable.

Proof

Let $G$ be a ($P_2+kP_1$, diamond)-free graph. If $\alpha (G) \le k$, then $\chi _{c}(G) \le k$ by Theorem 2. Assume $\alpha (G) \ge k+1$. Use the same terminologies and arguments as in the proof of Theorem 3, we can define a $k$-coloring of $G$ as follows:

$$ g(v) = {\left\{ \begin{array}{ll} 1, &{}\text {if} ~~ v \in S \\ 2, &{}\text {if} ~~ v \in N_G(s_0) \\ \min (R)+2, &{}\text {if} ~~ v \in Y_{R} ~\text {where}~ R = S {\setminus } (\{s_0\} \cup N_S(v)) ~\text {and}~\\ &{}~~~~ \min (R) \le k-2 \\ k, &{}\text {if} ~~ v \in Y_{R} ~\text {where}~ R = S {\setminus } (\{s_0\} \cup N_S(v)) ~\text {and}~ \\ &{}~~~~ \min (R) = k-1. \\ \end{array}\right. } $$

To claim that $g$ is a proper $k$-clique-coloring of $G$, suppose that $G$ has a monocolored maximal clique $Q$ of size at least two, say colored by $m$. Since $S$ is an independent set, $m \ne 1$. If $m \le k-1$, then $s_{m-2}$ is adjacent to all vertices of $Q$, a contradiction. Assume $m = k$. Then $Q \subseteq \bigcup \{Y_{R}~|~R \subseteq S {\setminus } \{s_0\}$ and $k-2 \le \min (R) \le k-1\}$. Since $Y_R = \emptyset$ for all $R \subseteq S {\setminus } \{s_0\}$ where $|R| \ge k-1$, we consider only $Y_R$ where $|R| \le k-2$. Thus if $k-2 \le \min (R) \le k-1$, then $R = \{s_1,s_2,\ldots ,s_{k-3},s_{t}\}$ where $k-2 \le t \le \alpha (G)-1$. Since $G$ is diamond-free and $\alpha (G)-1 \ge k$, $Y_{R}$ is an independent set, and then $|Q \cap Y_{R}| \le 1$ for each $R \subseteq S {\setminus } \{s_0\}$. If $|Q| \ge 3$, then there exists a diamond induced by a vertex in $S {\setminus } \{s_0\}$ and three vertices in $Q$, a contradiction. So $|Q| = 2$. Let $Q \subseteq Y_{R_1} \cup Y_{R_2}$ for some $R_1,R_2 \subseteq S {\setminus } \{s_0\}$ where $R_1 \ne R_2$ and $k-2 \le \min (R_1),\min (R_2) \le k-1$. Then $|R_1 \cup R_2| \le k-1$. Since $\alpha (G)-1 \ge k$, there exists a vertex in $S {\setminus } \{s_0\}$ that is adjacent to both vertices of $Q$, a contradiction. Hence $\chi _{c}(G) \le k$.

Similarly to ($P_2+kP_1$)-free graphs, the result for ($P_3+kP_1$)-free graphs in Theorem 4 has not been proved to be sharp. Theorem 6 gives its subclass of graphs using at most $k+1$ colors.

Theorem 6

For $k \ge 3$, a $(P_3+kP_1$, diamond$)$-free graph is $(k+1)$-clique-colorable.

Proof

Let $G$ be a $(P_3+kP_1$, diamond$)$-free graph. If $\alpha (G) \le k+1$, then $\chi _{c}(G) \le k+1$ by Theorem 2. Assume $\alpha (G) \ge k+2$. Use the same terminologies and arguments as in the proof of Theorem 4, we can define a ($k+1$)-coloring of $G$ as follows:

$$ g(v) = {\left\{ \begin{array}{ll} 1, &{}\text {if} ~~~ v \in S \\ 2, &{}\text {if} ~~~ v \in \mathop {\bigcup }\nolimits _{i=1}^{\alpha (G)}X_i \\ \min (R)+2, &{}\text {if} ~~~ v \in Y_{R} ~\text {where}~ R = S {\setminus } N_S(v) ~\text {and}~ \min (R) \le k-1 \\ k+1, &{}\text {if} ~~~ v \in Y_{R} ~\text {where}~ R = S {\setminus } N_S(v) ~\text {and}~ \min (R) = k. \end{array}\right. } $$

Suppose that $G$ has a monocolored maximal clique $Q$ of size at least two, say colored by $m$. If $m$ = 2, then $Q \subseteq X_i$ for some $i$; so $s_i$ is adjacent to all vertices of $Q$, a contradiction. If $3 \le m \le k$, then $s_{m-2}$ is adjacent to all vertices of $Q$, a contradiction. Assume $m = k+1$. Then $Q \subseteq \bigcup \{Y_{R}~|~R \subseteq S$ and $k-1 \le \min (R) \le k\}$. Since $G$ is diamond-free and $\alpha (G) \ge k+2$, $Y_{R}$ is an independent set. Thus $|Q \cap Y_{R}| \le 1$ for each $R \subseteq S$. If $|Q| \ge 3$, then there exist a vertex in $S$ together with any three vertices in $Q$ which induce a diamond, a contradiction. So $|Q| = 2$. Since $\alpha (G) \ge k+2$, there exists a vertex in $S$ that is adjacent to both vertices of $Q$, a contradiction. Hence $\chi _{c}(G) \le k+1$.

Since the 4-chromatic Mycielski’s graph $G_4$ is $(P_3+3P_1$, diamond)-free, the upper bound in Theorem 6 for the case $k$ = 3 is sharp.