# Borodin-Kostochka conjecture and Partitioning a graph into classes with no
clique of specified size

Yaser Rowshan1 1Y. Rowshan, Department of Mathematics, Institute for Advanced
Studies in Basic Sciences (IASBS), Zanjan 45137-66731, Iran
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

For a given graph $H$ and the graphical properties $P_{1},P_{2},\ldots,P_{k}$,
a graph $H$ is said to be $(V_{1},V_{2},\ldots,V_{k})$-partitionable if there
exists a partition of $V(H)$ into $k$-sets $V_{1},V_{2}\ldots,V_{k}$, such
that for each $i\in[k]$, the subgraph induced by $V_{i}$ has the property
$P_{i}$. In $1979$, Bollobás and Manvel showed that for a graph $H$ with
maximum degree $\Delta(H)\geq 3$ and clique number $\omega(H)\leq\Delta(H)$,
if $\Delta(H)=p+q$, then there exists a $(V_{1},V_{2})$-partition of $V(H)$,
such that $\Delta(H[V_{1}])\leq p$, $\Delta(H[V_{2}])\leq q$, $H[V_{1}]$ is
$(p-1)$-degenerate, and $H[V_{2}]$ is $(q-1)$-degenerate.

Assume that $p_{1}\geq p_{2}\geq\cdots\geq p_{k}\geq 2$ are $k$ positive
integers and $\sum_{i=1}^{k}p_{i}=\Delta(H)-1+k$. Assume that for each
$i\in[k]$ the properties $P_{i}$ means that $\omega(H[V_{i}])\leq p_{i}-1$. Is
$H$ a $(V_{1},\ldots,V_{k})$-partitionable graph?

In 1977, Borodin and Kostochka conjectured that any graph $H$ with maximum
degree $\Delta(H)\geq 9$ and without $K_{\Delta(H)}$ as a subgraph, has
chromatic number at most $\Delta(H)-1$. Reed proved that the conjecture holds
whenever $\Delta(G)\geq 10^{14}$. When $p_{1}=2$ and $\Delta(H)\geq 9$, the
above question is the Borodin and Kostochka conjecture. Therefore, when all
$p_{i}$s are equal to $2$ and $\Delta(H)\leq 8$, the answer to the above
question is negative. Let $H$ is a graph with maximum degree $\Delta$, and
clique number $\omega(H)$, where $\omega(H)\leq\Delta-1$. In this article, we
intend to study this question when $k\geq 2$ and $\Delta\geq 13$. In
particular as an analogue of the Borodin-Kostochka conjecture, for the case
that $\Delta\geq 13$ and $p_{i}\geq 2$ we prove that the above question is
true.

###### Key words and phrases:

Vertex partitionable, Clique number, Degenerate graphs, Borodin-Kostochka
conjecture.

###### 2010 Mathematics Subject Classification:

05C69, 05C35, 05C15.

##  1\. Introduction

All graphs considered in this article are undirected, simple, and finite. For
a given graph $H=(V(H),E(H))$, the degree and neighbors of $v\in V(H)$ are
denoted by $\deg_{H}{(v)}$ ($\deg{(v)}$) and $N_{H}(v)$($N(v)$), respectively.
The maximum degree of $H$ is denoted by $\Delta(H)$ and the minimum degree of
$H$ is denoted by $\delta(H)$. Suppose that $V^{\prime}$ and
$V^{\prime\prime}$ be two disjoint subsets of $V(H)$, we use
$E[V^{\prime},V^{\prime\prime}]$ to denote the set of edges between the
bipartition $(V^{\prime},V^{\prime\prime})$ of $H$. Suppose that $W$ is any
subset of $V(H)$, the induced subgraph $H[W]$ is the graph whose vertex set is
$W$ and whose edge set consists of all of the edges in $E(H)$ that have both
endpoints in $W$. The clique number $\omega(H)$ of a graph $H$ is the largest
integer $\omega$, so that $H$ contains a complete subgraph of size $\omega$.
For a given graph $H$ and the graphical properties $P_{1},P_{2},\ldots,P_{k}$,
a graph $H$ is said to be $(V_{1},V_{2},\ldots,V_{k})$-partitionable if there
exists a partition of $V(H)$ into $k$-sets $V_{1},V_{2}\ldots,V_{k}$, such
that for each $i\in[k]$, the subgraph induced by $V_{i}$ has the property
$P_{i}$. For more results on $(V_{1},\ldots,V_{k})$-partitionable see e.g.
[16, 2, 3, 1, 17, 10]. A graph $H$ is $k$-degenerate if every subgraph of $H$
contains a vertex of degree at most $k$. For the case that $k=2$, Bollobás and
Manvel in [4] have shown the following result regarding
$(V_{1},V_{2})$-partition.

######  Lemma A.

[4] Suppose that $H$ is a graph with maximum degree $\Delta(H)\geq 3$ and
clique number $\omega(H)\leq\Delta(H)$. If $\Delta(H)=p+q$, then there exists
a $(V_{1},V_{2})$-partition of $V(H)$, such that $\Delta(H[V_{1}])\leq p$,
$\Delta(H[V_{2}])\leq q$, $H[V_{1}]$ is $(p-1)$-degenerate, and $H[V_{2}]$ is
$(q-1)$-degenerate.

As a generalization of Brooks’ Theorem, Catlin showed that every graph $H$
with $\Delta(H)\geq 3$ without $K_{\Delta(H)+1}$ as a subgraph, has a
$\Delta(H)$-coloring such that one of the color classes is a maximum
independent set [7]. The author and Taherkhani, in [14], have shown the
following theorem.

######  Theorem A.

[14] Let $d_{1},d_{2}\ldots,d_{k}$ be $k$ positive integers. Assume that
$G_{1},G_{2}\ldots,G_{k}$ are connected graphs with minimum degrees
$d_{1},d_{2}\ldots,d_{k}$, respectively, and $H$ is a connected graph with
maximum degree $\Delta(H)$ where $\Delta(H)=\sum_{i=1}^{k}d_{k}$. Assume that
$G_{1},G_{2},\ldots,G_{k}$, and $H$ satisfy the following conditions:

  * •

If $k=1$, then $H$ is not isomorphic to $G_{1}$.

  * •

If $G_{i}$ is isomorphic to $K_{d_{i}+1}$ for each $1\leq i\leq k$, then $H$
is not isomorphic to $K_{\Delta(H)+1}$.

  * •

If $G_{i}$ is isomorphic to $K_{2}$ for each $1\leq i\leq k$, then $H$ is
neither an odd cycle nor a complete graph.

Then, there is a partition of vertices of $H$ to $V_{1},V_{2}\ldots,V_{k}$
such that each $G_{i}\nsubseteq H[V_{i}]$ and moreover one of $V_{i}$s can be
chosen in a way that $H[V_{i}]$ be a maximum induced $G_{i}$-free subgraph in
$H$(i.e $H$ contain no copy of $G$).

In this article, for a graph $H$ and $k$ positive integers $p_{1}\geq
p_{2}\geq\cdots\geq p_{k}\geq 2$, instead to
$(V_{1},\ldots,V_{k})$-partitionable, we say $H$ is
$(K_{p_{1}},\ldots,K_{p_{k}})$-partitionable if there exists a partition of
$V(H)$ into $k$-sets, $V_{1},V_{2}\ldots,V_{k}$, such that for each $i\leq k$
we have $\omega(H[V_{i}])\leq p_{i}-1$.

######  Question 0.1.

Suppose that $H$ is a graph with $\Delta(H)\geq 6$ and clique number
$\omega(H)$, where $\omega(H)\leq\Delta(H)-1$. Assume that $p_{1}\geq
p_{2}\geq\cdots\geq p_{k}\geq 2$ are $k$ positive integers and
$\sum_{i=1}^{k}p_{i}=\Delta(H)-1+k$. Is $H$ a
$(K_{p_{1}},\ldots,K_{p_{k}})$-partitionable graph?

In $1977$, Borodin and Kostochka conjectured that Brooks’ bound can be further
improved if $\Delta(H)\geq 9$.

######  Conjecture 1.

[5] For a graph $H$, if $\Delta(H)\geq 9$, then
$\chi(H)\leq\max\\{\omega(H),\Delta(H)-1\\}$.

By Brooks’theorem, each graph $H$ with $\chi(H)>\Delta(H)\geq 9$ contains
$K_{\Delta(H)+1}$. So the Borodin-Kostochka conjecture is equivalent to the
statement that each $H$ with $\chi(H)=\Delta(H)\geq 9$ contains
$K_{\Delta(H)}$. In $1999$, Reed proved that the Conjecture 1 holds whenever
$\Delta(G)\geq 10^{14}$ [13]. Note that the above question for $k=1$ is
clearly true. Also, note that the above question in case that $p_{1}=2$ (i.e.
all $p_{i}$s are equal to $2$) and $\Delta(H)\geq 9$, is the Borodin and
Kostochka conjecture. Therefore, when all $p_{i}$s are equal to $2$ and
$\Delta(H)\leq 8$, the answer to the above question is negative. Let
$\operatorname{\mathcal{G}}$ be a class of graphs such that the Borodin-
Kostochka conjecture is true for each $H\in\operatorname{\mathcal{G}}$.
Therefore for each $H\in\operatorname{\mathcal{G}}$ we have
$\chi(H)\leq\Delta-1$. Hence by $\sum_{i=1}^{k}(p_{i}-1)=\Delta(H)-1$ it can
be said that for each $H\in\operatorname{\mathcal{G}}$, $V(H)$ can be
decomposed into $k$-sets $V_{1},V_{2}\ldots,V_{k}$, such that for each $i\leq
k$, we have $\chi(H[V_{i}])\leq p_{i}-1$, that is $\omega(H[V_{i}])\leq
p_{i}-1$ for each $i\leq k$. Therefore, if the Borodin and Kostochka
conjecture holds and in Question 0.1 we have $p_{1}\geq 3$ and $\Delta(H)\geq
9$, then the answer of Question 0.1 is positive.

So assume that $H$ is a counter-example to the Borodin-Kostochka conjecture of
maximum degree $\Delta$, and clique number $\omega(H)$, where
$\omega(H)\leq\Delta-1$. When $\chi(H)=\Delta(H)$, there are series of
interesting and useful results that show $\omega(H)$ must be close to
$\Delta(H).$ As the first result, Borodin and Kostochka showed that if
$\chi(H)=\Delta(H)\geq 7$, then $H$ contains $K_{\frac{\Delta(H)+1}{2}}$ [6].
Mozhan proved that $\omega(H)\geq\Delta(H)-3$, when $\Delta(H)\geq 31$[11].
Finally, Cranston and Rabern strengthened the Mozhan’s result by weakening the
condition to $\Delta(H)\geq 13$ [8].

In this article, we shall show the following theorems are valid.

######  Theorem 1.

Assume that $\Delta$, $p_{1}\geq p_{2}\geq\cdots\geq p_{k}\geq 2$ are $k+1$
positive integers where $p_{1}+p_{2}\geq 14$ and
$\sum_{i=1}^{k}p_{i}=\Delta-1+k$. If $H$ is a countere-example for the
Borodin-Kostochka conjecture with $\Delta(H)=\Delta\geq 13$, then $H$ is a
$(K_{p_{1}},\ldots,K_{p_{k}})$-partitionable.

######  Theorem 2.

Suppose that $H$ is a graph with $\Delta(H)\geq 13$, $\chi(H)=\Delta(H)$, and
clique number $\omega(H)\leq\Delta(H)-1$. Also, suppose that $p_{1}\geq
p_{2}\geq\cdots\geq p_{k}\geq 2,$ are $k$ positive integers where
$\sum_{i=1}^{k}p_{i}=\Delta(H)-1+k$. Let $V^{\prime}$ is a subset of $V(H)$,
such that $H[V^{\prime}]\cong K_{\omega(H)}$. If $H^{\prime}=H\setminus
V^{\prime}$ is a $(K_{p_{1}},\ldots,K_{p_{k}})$-partitionable and moreover one
of $V_{i}$s can be chosen in a way that $H^{\prime}[V^{\prime}_{i}]$ be a
maximum induced $K_{p_{1}}$-free subgraph in $H^{\prime}$, $H$ is a
$(K_{p_{1}},\ldots,K_{p_{k}})$-partitionable and moreover one of $V_{i}$s can
be chosen in a way that $H[V_{i}]$ be a maximum induced $K_{p_{1}}$-free
subgraph in $H$.

As a direct consequence of Theorem 1, and Theorem 2, one can see that if
$k=2$, $p_{1}=p_{2}=p\geq 7$, $\Delta\geq 13$, and $H$ be a graph with
$\omega(H)\leq\Delta(H)-1$, then
$\chi_{{}_{K_{p}}}(H)\leq\lceil{\Delta(H)-1\over
p-1}\rceil=2<\lceil{\Delta(H)\over p-1}\rceil=3$, which is better than the
result of Theorem A. Another proof of theorem 1 can be seen in [15].

##  2\. 2-vertex partition of a graph into two induced subgraphs not
containing prescribed cliqes

In this section, we prove the main results for the case that $k=2$. In
particular we prove the following theorem.

######  Theorem 3.

Suppose that $H$ be a graph with $\Delta(H)\geq 13$ and clique number
$\omega(H)$, where $\omega(H)\leq\Delta(H)-1$. Assume that $p$ and $q$ are two
positive integers where $p+q=\Delta(H)+1$. Then $H$ is a
$(K_{p_{1}},K_{p_{2}})$-partitionable.

With the assumptions of Theorem 3, if $\chi(H)\leq\Delta-1$, then it can be
said that there exists a $(V_{1},V_{2})$-decomposition of $V(H)$, so that
$\chi(H[V_{1}])\leq p-1$ and $\chi(H[V_{2}])\leq q-1$. Hence, in this case the
correctness of Theorem 3, is obvious. Hence, we may suppose that
$\chi(H)=\Delta$. That is assume that $H$ is a counter-example to the Borodin-
Kostochka conjecture. By the following results of Cranston and Rabern, we can
suppose that $\omega(H)\in\\{\Delta-3,\Delta-2,\Delta-1\\}$.

######  Theorem 4.

[8] If $H$ is a graph with $\chi(H)\geq\Delta(H)\geq 13$, then
$\omega(H)\geq\Delta(H)-3$.

To prove Theorem 3, we need the following results.

######  Proposition 5.

Let $H$ be a graph, where $\Delta(H)=\Delta$ and $\omega(H)=\omega$. Also,
assume that $K_{\omega}$ is a clique of size $\omega$ in $H$. Hence, for each
$v,v^{\prime}\in V(H)\setminus V(K_{\omega})$, such that $vv^{\prime}\in
E(H)$, there exists two members $w,w^{\prime}(w\neq w^{\prime})$ of
$V(K_{\omega})$, such that $vw,v^{\prime}w^{\prime}\notin E(H)$.

###### Proof.

In otherwise, one can find a clique of size at least $\omega+1$ in $H$, which
is a contradiction. ∎

The next result was proved by Reed in [13].

######  Lemma 6.

[13] If $H$ is a minimal counter-example to the Borodin-Kostochka conjecture
of maximum degree $\Delta$, then its $\Delta-1$ cliques are disjoint.

Now, we will use the idea used to prove Lemma 6, and prove the following
theorem.

######  Theorem 7.

If $H$ is a minimal counter-example to Theorem 3 for the case that
$\Delta(H)=\Delta$, $\omega(H)=\Delta-1$ and $p\geq q\geq 5$, then its
$\Delta-1$ cliques are disjoint.

###### Proof.

To prove, we consider the following two claims.

######  Claim 8.

No two $\Delta-1$ cliques intersect in $\Delta-2$ vertices.

###### Proof of Claim 8.

Suppose that there are two $\Delta-1$ cliques, say $K$ and $K^{\prime}$, which
intersect in a $\Delta-2$ clique $K^{\prime\prime}$ and assume that $x\in
K\setminus K^{\prime\prime}$, $y\in K^{\prime}\setminus K^{\prime\prime}$. We
note that each of these two vertices is adjacent to every element of
$K^{\prime\prime}$, that is every vertex of $K^{\prime\prime}$ has degree
$\Delta-1$ in $K\cup K^{\prime}$. Therefore, $|N(z)\cap(H\setminus(K\cup
K^{\prime}))|\leq 1$ for each $z\in V(K^{\prime\prime})$. Now, there is on
edge $xy\notin E(H)$, otherwise this copy along with $K^{\prime\prime}$ forms
a $\Delta$ clique, a contradiction to $\omega(H)=\Delta-1$. Therefore, no
$\Delta-1$ clique intersects in $x$ and $y$. Let
$H^{\prime}=H\setminus\\{x,y\\}$. By the minimality of $H$, there exaists a
$(S_{1},S_{2})$-decomposetion of $V(H^{\prime})$, where $H^{\prime}[S_{1}]$ is
$K_{p}$-free and $H^{\prime}[S_{2}]$ is $K_{q}$-free. Also, as
$|K^{\prime\prime}|=\Delta-2$, without loss of generality we can suppose that
$|S_{1}\cap V(K^{\prime\prime})|=|V_{1}|=p-1$ and $|S_{2}\cap
V(K^{\prime\prime})|=|V_{2}|=q-2$. Now, consider $(W_{1},W_{2})$-decomposetion
of $V(H)$, where $W_{1}=S_{1}$ and $W_{2}=S_{2}\cup\\{x,y\\}$. If $H[W_{2}]$
is $K_{q}$-free, which contradicts the assumption that $H$ is a minimal
counter-example and the proof is complete. So, we may suppose that there
exists at least one copy of $K_{q}$ in $H[W_{2}]$. Since $xy\notin E(H)$, no
$q$-clique intersects in $x$ and $y$ in $H[W_{2}]$. Therefore there exists a
vertex $w$ of $S_{2}\setminus V_{2}$, such that $V_{2}\subseteq N(w)$ and $w$
is adjacent to at least one vertex of $\\{x,y\\}$ in $H$. Without loss of
generality, assume that $xw\in E(H)$, that is $H[V_{2}\cup\\{x,w\\}]\cong
K_{q}$. In this case, we claim that $V_{1}\subseteq N(w)$. Otherwise, if there
exists a vertex $v$ of $V_{1}$, such that $vw\notin E(H)$, then we set
$S^{\prime}_{1}=(S_{1}\setminus\\{v\\})\cup\\{u\\}$ and
$S^{\prime}_{2}=(S_{2}\setminus\\{u\\})\cup\\{v\\}$, where $u\in V_{2}$. Now,
since $vw\notin E(H)$, $V_{2}\setminus\\{v\\}\subseteq N(w)$, $|N(z)\cap
S_{2}|\leq 1$ for each $z\in V_{2}$ and $q\geq 5$, it is easy to check that
$H[S^{\prime}_{2}]$ is $K_{q}$-free. Also, since $|N(z)\cap(S_{1}\setminus
V_{1})|\leq 1$ for each $z\in V_{1}$ and $|N(u)\cap S_{2}|=q+1$, we have
$|N(u)\cap S_{1}|=|V_{1}\setminus\\{v\\}|=p-2$, that is $H[S^{\prime}_{1}]$ is
$K_{p}$-free. Which contradicts the assumption that $H$ is a minimal counter-
example. Hence, assume that $V_{1}\subseteq N(w)$, that is
$H[V(K^{\prime\prime})\cup\\{x,w\\}]=K_{\Delta}$, a contradiction again. Thus,
for any vertex $w$ of $S_{2}$, we have $V_{2}\nsubseteq N(w)$. Therefore as
$xy\notin E(H)$ and $|N(z)\cap(H\setminus(K\cup K^{\prime}))|\leq 1$ for each
$z\in V(K^{\prime\prime})$, one can say that $H[W_{2}]$ is $K_{q}$-free, it
contradicts the assumption that $H$ is a minimal counter-example. Therfore the
cliam is true. ∎

######  Claim 9.

No two $\Delta-1$ cliques intersect in $\Delta-3$ vertices.

###### Proof of Claim 9.

Suppose that there are two $\Delta-1$ cliques, say $K$ and $K^{\prime}$, which
intersect in a $\Delta-3$ clique $K^{\prime\prime}$. Also, assume that $x,y\in
K\setminus K^{\prime\prime}$ and $x^{\prime},y^{\prime}\in K^{\prime}\setminus
K^{\prime\prime}$. We note that each of these four vertices is adjacent to
every element of $K^{\prime\prime}$. Therfore $|N(z)\cap(H\setminus(K\cup
K^{\prime}))|=0$ for each $z\in V(K^{\prime\prime})$. Now, there is no copy of
$K_{3}$ in the induced graph by $\\{x,x^{\prime},y,y^{\prime}\\}$. Otherwise
this copy along with $K^{\prime\prime}$ forms a $\Delta$ clique, a
contradiction to $\omega(H)=\Delta-1$. Thus, we can assume that
$xx^{\prime},yy^{\prime}\notin E(H)$. Therefore, no $\Delta-1$ clique
intersects in $\\{x,x^{\prime}\\}$ and $\\{y,y^{\prime}\\}$. Let
$H^{\prime\prime}=H\setminus(K\cup K^{\prime})$, by the minimality of $H$,
there exists a $(S^{\prime}_{1},S^{\prime}_{2})$-decomposetion of
$V(H^{\prime\prime})$, sush that $H^{\prime\prime}[S^{\prime}_{1}]$ is
$K_{p}$-free and $H^{\prime\prime}[S^{\prime}_{2}]$ is $K_{q}$-free. Also,
since $|K^{\prime\prime}|=\Delta-3$, one cane assume that there exists a
$(V_{1},V_{2})$-decomposetion of $V(K^{\prime\prime})$, such that
$H[V_{1}]\cong K_{p-2}$ and $H[V_{2}]\cong K_{q-2}$. Now, set
$H^{\prime}=H^{\prime\prime}\cup
K^{\prime\prime}=H\setminus\\{x,x^{\prime},y,y^{\prime}\\}$ and concider
$(S_{1},S_{2})$-decomposetion of $V(H^{\prime})$ such that
$S_{i}=S^{\prime}_{i}\cup V_{i}$ for $i=1,2$. Since every vertex of
$K^{\prime\prime}$ has degree $\Delta$ in $K\cup K^{\prime}$ for rach $i=1,2$,
one can check that $H^{\prime}[V_{i}]$ is a connected component in
$H^{\prime}[S_{i}]$. Now, consider $W_{1}=S_{1}\cup\\{x,x^{\prime}\\}$ and
$W_{2}=S_{2}\cup\\{y,y^{\prime}\\}$. Since $xx^{\prime},yy^{\prime}\notin
E(H)$, and no $\Delta-1$ clique intersects in $\\{x,x^{\prime}\\}$ and
$\\{y,y^{\prime}\\}$, also as $\Delta\geq 9$, $p\geq 5,q\geq 5$,
$|N(z^{\prime})\cap S_{i}|\leq 2$ for each
$z^{\prime}\in\\{x,x^{\prime},y,y^{\prime}\\}$ and $|N(z)\cap
S^{\prime}_{i}|=0$ for each $z\in V(K^{\prime\prime})$ and each
$i\in\\{1,2\\}$, it is easy to check that $H[W_{1}]$ is $K_{p}$-free and
$H[W_{2}]$ is $K_{p}$-free, which contradicts the assumption that $H$ is a
minimal counter-example. Hence the claim is true. ∎

By $\Delta(H)=\Delta$, it can be said that, no two $\Delta-1$ cliques
intersect in fewer than $\Delta-3$ vertices. Otherwise, there is a vertex of
$H$ with degree at least $\Delta+1$, which is impossible. Therefore, by Claims
8 and 9 the proof is complete. ∎

Now, in the following results by using Theorem 7, we prove that Theorem 3
holds when $\omega(H)=\Delta-1$ and $p\geq q\geq 5$.

######  Fact 10.

Theorem 3 holds for the case that $\omega(H)=\Delta-1$, and $p\geq q\geq 5$.

###### Proof of Fact 10.

Without loss of generality we may assume that $H$ is a minimal counter-example
of Theorem 3 with maximum degree $\Delta$ and $\omega(H)=\Delta-1$. Let $K$ is
a $\Delta-1$ clique of $H$. Set $H^{\prime}=H\setminus K$. Hence, each vertex
of $K$ has at most two adjacents in $H^{\prime}$ and by Theorem 7, any vertex
of $H^{\prime}$ has at most $\Delta-3$ neighbors in $K$. Since $H$ is a
minimal counter-example, there exists a $(W_{1},W_{2})$-decomposition of
$V(H^{\prime})$, such that $H^{\prime}[W_{1}]$ is $K_{p}$-free and
$H^{\prime}[W_{2}]$ is $K_{q}$-free. Also, as $|K|=\Delta-1$, there exists a
$(V_{1},V_{2})$-decomposition of $V(K)$, such that $|V_{1}|=p-1$ and
$|V_{2}|=q-1$. So, it is clear that $H[V_{1}]$ is $K_{p}$-free and $H[V_{2}]$
is $K_{q}$-free. Set $\operatorname{\mathcal{F}}$ as follows.

$\operatorname{\mathcal{F}}=\\{(V^{\prime},V^{\prime\prime})~{}~{}|~{}~{}V^{\prime}\cap
V^{\prime\prime}=\emptyset,~{}V^{\prime}\cup
V^{\prime\prime}=V(K),~{}|V^{\prime}|=p-1,|V^{\prime\prime}|=q-1\\}.$

For each $i\in[|\operatorname{\mathcal{F}}|]$, define
$e_{i}=|E(H[W_{1},V_{i}])|+|E(H[W_{2},V^{\prime}_{i}])|$ where,
$(V_{i},V^{\prime}_{i})$ is a member of $\operatorname{\mathcal{F}}$. Without
loss of generality we may suppose that
$e_{1}=|E(H[W_{1},V_{1}])|+|E(H[W_{2},V_{1}^{\prime}])|\leq|E(H[W_{1},V_{i}])|+|E(H[W_{2},V_{i}^{\prime}])|$
for each $(V_{i},V_{i}^{\prime})\in\operatorname{\mathcal{F}}$. Now, we have
the following claims.

######  Claim 11.

If there exists a vertex $v$ of $V_{1}(V^{\prime}_{1})$, such that $|N(v)\cap
W_{1}(W_{2})|=2$, then for each $v^{\prime}\in V^{\prime}_{1}(V_{1})$ we have
$|N(v^{\prime})\cap W_{2}(W_{1})|=0$. Also, if there exists a vertex $v$ of
$V_{1}(V^{\prime}_{1})$, such that $|N(v)\cap W_{1}(W_{2})|=1$, then for each
$v^{\prime}\in V^{\prime}_{1}(V_{1})$ we have $|N(v^{\prime})\cap
W_{2}(W_{1})|\leq 1$.

###### Proof of Claim 11.

Without loss of generality assume that $|N(v)\cap W_{1}|=2$ for some $v\in
V_{1}$ and on contrary, suppose that there exists a vertex $v^{\prime}$ of
$V_{1}^{\prime}$, such that $|N(v^{\prime})\cap W_{2}|\geq 1$. In this case,
one can check that
$(V_{2},V^{\prime}_{2})=(V_{1}\setminus\\{v\\}\cup\\{v^{\prime}\\},V^{\prime}_{1}\setminus\\{v^{\prime}\\}\cup\\{v\\})\in\operatorname{\mathcal{F}}$.
Also as each vertex of $K$ has at most two adjacents in $H^{\prime}$, then it
is easy to say that
$e_{2}=|E(H[W_{1},V_{2}])|+|E(H[W_{2},V_{2}^{\prime}])|\leq e_{1}-2$, which is
a contradiction to the minimality of $e_{1}$. For other cases the proof is the
same and the claim is true. ∎

######  Claim 12.

If there exist two vertices $w,w^{\prime}$ of $W_{1}$, such that:

$|N(w)\cap N(w^{\prime})\cap V_{1}|\geq p-2,$

or if there exist two vertices $w,w^{\prime}$ of $W_{2}$ such that:

$|N(w)\cap N(w^{\prime})\cap V_{1}^{\prime}|\geq q-2,$

then the proof is complete.

###### Proof of Claim 12.

Without loss of generality assume that $|N(w_{1})\cap N(w_{2})\cap V_{1}|\geq
p-2$ for some $w_{1},w_{2}\in W_{1}$. Also, we may suppose that
$M=\\{v_{1},\ldots,v_{p-2}\\}\subseteq N(w_{1})\cap N(w_{1})\cap V_{1}$. Since
$|M|=p-2\geq 3$, by Claim 11, we have $|N(v^{\prime})\cap W_{2}|=0$ for each
$v^{\prime}\in V_{1}^{\prime}$. Since each vertex of $K$ has at most two
adjacents in $H^{\prime}$ and $\\{w_{1},w_{2}\\}\subseteq N(v)$ for each $v\in
M$ and as any vertex of $H^{\prime}$ has at most $\Delta-3$ neighbors in $K$,
there exist at least two vertices $v_{1}^{\prime\prime},v_{2}^{\prime\prime}$
of $V(K)\setminus M$, such that $w_{i}v^{\prime\prime}_{i}\notin E(H)$ for
$i=1,2$. Now, we set $(V_{2},V^{\prime}_{2})$ as follows.

$(V_{2},V^{\prime}_{2})=(M\setminus\\{v_{1}\\}\cup\\{v^{\prime\prime}_{1},v^{\prime\prime}_{2}\\},V(K)\setminus
V_{2}).$

One can say that $(V_{2},V^{\prime}_{2})\in\operatorname{\mathcal{F}}$. As
$|M|\geq 3$, by Claim 11, we have $|N(v^{\prime})\cap W_{2}|=0$ for at least
$q-2$ members of $V_{2}^{\prime}$, which means that $H[V^{\prime}_{2}\cup
W_{2}]$ is $K_{q}$-free. Also, as
$v^{\prime\prime}_{1},v^{\prime\prime}_{2}\in V_{2}$,
$w_{1}v^{\prime\prime}_{1},w_{2}v^{\prime\prime}_{2}\notin E(H)$,
$M\setminus\\{v_{1}\\}\subseteq N(w_{i})$, each vertex of $V_{2}$ has at most
two adjacents in $W_{1}$, and $p\geq 5$, it is easy to check that $H[V_{2}\cup
W_{1}]$ is $K_{p}$-free. Hence, the proof is complete. ∎

Now, by the assumption that $H$ is a minimal counter-example of Theorem 3, one
can assume that there exists a copy of $K_{p}$ in $H[V_{1}\cup W_{1}]$ or
there is a copy of $K_{q}$ in $H[V_{2}\cup W_{2}]$. Without loss of generality
we may assume that $K^{\prime}=K_{p}\subseteq H[V_{1}\cup W_{1}]$. By
considering the vertices of $V(K^{\prime})$ and by Claim 12, one can assume
that $|V(K^{\prime})\cap V_{1}|=p-1$. Without loss of generality assume that
$w_{1}\in V(K^{\prime})\cap W_{1}$, that is $V_{1}\subseteq N(w_{1})$. Now, by
Claim 11, we have $|N(v^{\prime})\cap W_{2}|\leq 1$ for each $v^{\prime}\in
V_{2}^{\prime}$. Since each vertex of $K$ has at most two adjacents in
$H^{\prime}$, any vertex of $H^{\prime}$ has at most $\Delta-3$ neighbors in
$K$, and $w_{1}v\in E(H)$ for each $v\in V_{1}$, there exist at lest two
vertices $v_{1}^{\prime},v_{2}^{\prime}$ of $V^{\prime}_{1}$, such that
$w_{1}v^{\prime}_{i}\notin E(H)$. Now, we set $(V_{2},V^{\prime}_{2})$ as
follows.

$(V_{2},V^{\prime}_{2})=(V_{1}\setminus\\{v_{1}\\})\cup\\{v^{\prime}_{1}\\},V(K)\setminus
V_{2}).$

One can say that $(V_{2},V^{\prime}_{2})\in\operatorname{\mathcal{F}}$. If
$H[V_{2}\cup W_{1}]$ be $K_{p}$-free and $H[V^{\prime}_{2}\cup W_{2}]$ be
$K_{q}$-free, then the proof is complete. Also, if there exists a copy of
$K_{p}$ in $H[V_{2}\cup W_{1}]$, then as
$V_{2}\setminus\\{v^{\prime}_{1}\\}\subseteq N(w_{1})$, one can check that
there exist two vertices $w_{1},w_{2}$ of $W_{1}$, such that $|N(w_{1})\cap
N(w_{2})\cap V_{2}|=p-2$ and so the proof is complete by Claim 12. So, assume
that $H[V_{2}\cup W_{1}]$ is $K_{p}$-free and $H[V^{\prime}_{2}\cup W_{2}]$
has a copy $K^{\prime\prime}$ of $K_{q}$. By Claim 11 and as
$|N(v^{\prime})\cap W_{2}|\leq 1$ for each $v^{\prime}\in V^{\prime}_{2}$, one
can assume that there exists a member $w^{\prime}_{1}$ of $W_{2}$, so that
$V^{\prime}_{2}\subseteq N(w_{2})$ and
$V(K^{\prime\prime})=V^{\prime}_{2}\cup\\{w_{1}^{\prime}\\}$. As any vertex of
$H^{\prime}$ has at most $\Delta-3$ neighbors in $K$, there exists at least
one vertex $v_{2}$ of $V_{2}\setminus\\{v^{\prime}_{1}\\}$, such that
$w^{\prime}_{1}v_{2}\notin E(H)$. Now, we set $(V_{3},V^{\prime}_{3})$ as
follows.

$(V_{3},V^{\prime}_{3})=(V_{2}\setminus\\{v_{2}\\})\cup\\{v_{1}\\},V(K)\setminus
V_{2}).$

One can say that $(V_{3},V^{\prime}_{3})\in\operatorname{\mathcal{F}}$. Since
$V_{3}\setminus\\{v^{\prime}_{1}\\}\subseteq N(w_{1})$, $|N(v)\cap W_{1}|\leq
1$ for each $v\in V_{1}$, and $p\geq 5$, one can say that $H[V_{3}\cup W_{1}]$
is $K_{p}$-free. Also, as $V^{\prime}_{3}\setminus\\{v_{2}\\}\subseteq
N(w^{\prime}_{1})$, $|N(v^{\prime})\cap W_{2}|\leq 1$ for each $v^{\prime}\in
V_{1}^{\prime}$, and $q\geq 5$, one can check that $H[V^{\prime}_{3}\cup
W_{2}]$ is $K_{q}$-free, which contradicts the assumption that $H$ is a
minimal counter-example. Hence the assumption does not holds, and the proof of
the fact is complete. ∎

By Fact 10, Theorem 3 holds for the case that $\omega(H)=\Delta-1$. So, one
can suppose that $\omega(H)\leq\Delta-2$. Hence, by using Fact 10, we can
prove the following result.

######  Fact 13.

Theorem 3 holds for the case that $H$ is non-$\Delta$-regular graph,
$\omega(H)\leq\Delta-2$, and $p\geq q\geq 5$.

###### Proof of Fact 13.

As $H$ is a non-$\Delta$-regular graph, there exists at least one member $v$
of $V(H)$, such that $\deg(v)\leq\Delta-1$. Consider the complete graph
$K=K_{\Delta-1}$ and let $y$ be a vertex of $K$. Let $H^{\prime}=(H\cup
K)+vy$. It is clear that $H^{\prime}$ is a graph with
$\Delta(H^{\prime})=\Delta$ and $\omega(H^{\prime})=\Delta-1$. Therefore, by
Fact 10, there exists a $(V^{\prime}_{1},V^{\prime}_{2})$-decomposition of
$V(H^{\prime})$, such that $\omega(H^{\prime}[V^{\prime}_{1}])\leq p-1$ and
$\omega(H^{\prime}[V^{\prime}_{2}])\leq q-1$. Hence, as $H\subseteq
H^{\prime}$, one can say that there exists a $(V_{1},V_{2})$-decomposition of
$V(H)$, such that $\omega(H[V_{1}])\leq p-1$ and $\omega(H[V_{2}])\leq q-1$,
where $V_{1}=V(H)\cap V^{\prime}_{1}$ and $V_{2}=V(H)\cap V^{\prime}_{2}$.

∎

Therfore, by Fact 10 and Fact 13, suppose that $H$ is a $\Delta$-regular graph
with $\chi(H)=\Delta\geq 13$, and $\omega(H)\in\\{\Delta-2,\Delta-3\\}$.

######  Fact 14.

Theorem 3 holds for the case that $H$ is a $\Delta$-regular graph with
$\chi(H)=\Delta$, $\omega(H)=\Delta-2$, and $p\geq q\geq 6$.

###### Proof of Fact 14.

Without loss of generality we may suppose that $H$ is a minimal counter-
example of Theorem 3 where $H$ is a $\Delta$-regular, $\chi(H)=\Delta$, and
$\omega(H)=\Delta-2$. Suppose that $K$ is a $\Delta-2$ clique of $H$. Set
$H^{\prime}=H\setminus K$. Therefore, any member of $K$ has three adjacents in
$H^{\prime}$ and by $\omega(H)=\Delta-2$, any member of $H^{\prime}$ has at
most $\Delta-3$ neighbors in $K$. Since $H$ is a minimal counter-example, one
can suppose that there is a $(W_{1},W_{2})$-decomposition of $V(H^{\prime})$,
such that $H^{\prime}[W_{1}]$ is $K_{p}$-free and $H^{\prime}[W_{2}]$ is
$K_{q}$-free. Since $|K|=\Delta-2$, we can decompose $V(K)$ into
$(V^{\prime},V^{\prime\prime})$, where $|V^{\prime}|=p-1$ and
$|V^{\prime\prime}|=q-2$, or $|V^{\prime}|=p-2$ and $|V^{\prime\prime}|=q-1$.
It is clear that in any case, $H[V^{\prime}]$ is $K_{p}$-free and
$H[V^{\prime\prime}]$ is $K_{q}$-free. Set $\operatorname{\mathcal{F}}$ as
follows.

$\operatorname{\mathcal{F}}=\\{(V^{\prime},V^{\prime\prime})~{}~{}|~{}~{}V^{\prime}\cap
V^{\prime\prime}=\emptyset,~{}V^{\prime}\cup
V^{\prime\prime}=V(K),~{}p-2\leq|V^{\prime}|\leq
p-1,q-2\leq|V^{\prime\prime}|\leq q-1\\}.$

For each $i\in[|\operatorname{\mathcal{F}}|]$, assume that
$e_{i}=|E(H[W_{1},V_{i}])|+|E(H[W_{2},V_{i}^{\prime}])|$, where
$(V_{i},V^{\prime}_{i})$ is a member of $\operatorname{\mathcal{F}}$. Without
loss of generality we may suppose that
$e_{1}=|E(H[W_{1},V_{1}])|+|E(H[W_{2},V^{\prime}_{1}])|\leq|E(H[W_{1},V_{i}])|+|E(H[W_{2},V_{i}^{\prime}])|$
for each $(V_{i},V^{\prime}_{i})\in\operatorname{\mathcal{F}}$. Now, we have
the following claims.

######  Claim 15.

If there exists a vertex $v$ of $V_{1}(V^{\prime}_{1})$, such that $|N(v)\cap
W_{1}(W_{2})|\geq 2$, then for each $v^{\prime}\in V^{\prime}_{1}(V_{1})$, we
have $|N(v^{\prime})\cap W_{2}(W_{1})|\leq 1$. Also, if there exists a vertex
$v$ of $V_{1}(V^{\prime}_{1})$, such that $|N(v)\cap W_{1}(W_{2})|=3$, then
for each $v^{\prime}\in V^{\prime}_{1}(V_{1})$, we have $|N(v^{\prime})\cap
W_{2}(W_{1})|=0$.

###### Proof of Claim 15.

Without loss of generality assume that $|N(v)\cap W_{1}|=2$ for some $v\in
V_{1}$. Also, on contrary, suppose that there exists a vertex $v^{\prime}$ of
$V_{1}^{\prime}$, such that $|N(v^{\prime})\cap W_{1}|\geq 2$. Hence, one can
check that
$(V_{2},V_{2}^{\prime})=(V_{1}\setminus\\{v\\}\cup\\{v^{\prime}\\},V^{\prime}_{1}\setminus\\{v^{\prime}\\}\cup\\{v\\})\in\operatorname{\mathcal{F}}$.
Also, as any member of $K$ has three adjacents in $H^{\prime}$, then it is
easy to say that $e_{2}=|E(H[W_{1},V_{2}])|+|E(H[W_{2},V_{2}^{\prime}])|\leq
e_{1}-2$, which is a contradiction to the minimality of $e_{1}$ and the proof
is complete. For other cases the proof is the same and the claim is true. ∎

######  Claim 16.

If $|V_{1}|=p-1(~{}or~{}|V_{2}|=q-1)$, then for each vertex $v$ of
$V_{1}(V_{2})$, we have $|N(v)\cap W_{1}(W_{2})|\leq 1$.

###### Proof of Claim 16.

Without loss of generality assume that $|V_{1}|=p-1$ and $|N(v)\cap W_{1}|\geq
2$ for some $v\in V_{1}$. Now, set
$(V_{2},V_{2}^{\prime})=(V_{1}\setminus\\{v\\},V^{\prime}_{1}\cup\\{v\\})\in\operatorname{\mathcal{F}}$.
Hence, as any member of $V(K)$ has three neighbors in $V(H^{\prime})$, it is
easy to say that $e_{2}=|E(H[W_{1},V_{2}])|+|E(H[W_{2},V_{2}^{\prime}])|\leq
e_{1}-1$, which is a contradiction to the minimality of $e_{1}$. ∎

So, as $p-2\leq|V_{1}|\leq p-1$ and $q-2\leq|V_{2}|\leq q-1$, without loss of
generality we may assume that $|V_{1}|=p-1$ and $|V_{2}|=q-2$. Now, we have a
claim as follows.

######  Claim 17.

$H[V_{1}\cup W_{1}]$ is $K_{p}$-free.

###### Proof of Claim 17.

On contrary, assume that $K^{\prime}$ is a copy of $K_{p}$ in $H[V_{1}\cup
W_{1}]$. As $|V_{1}|=p-1$, by Claim 16, there should be a vertex $w_{1}$ of
$W_{1}$, such that $V_{1}\subseteq N(w_{1})$ and $|N(v)\cap W_{1}|=1$ for each
$v\in V_{1}$. Also, by Claim 15, one can say that $|N(v^{\prime})\cap
W_{2}|\leq 2$ for each $v^{\prime}\in V_{2}$. As any vertex of $W_{1}$ has at
most $\Delta-3$ neighbors in $K$, there exists at least one vertex
$v^{\prime}_{1}$ of $V_{2}$, such that $w_{1}v^{\prime}_{1}\notin E(H)$. Now,
we set $(V^{\prime}_{1},V^{\prime}_{2})$ as follows.

$(V^{\prime}_{1},V^{\prime}_{2})=(V_{1}\setminus\\{v_{1}\\})\cup\\{v^{\prime}_{1}\\},V(K)\setminus
V^{\prime}_{1}).$

It is clear that
$(V^{\prime}_{1},V^{\prime}_{2})\in\operatorname{\mathcal{F}}$. Also, as
$|V^{\prime}_{1}|=p-1\geq 5$ and $w_{1}v^{\prime}_{1}\notin E(H)$, by Claim
16, it can be said that $H[V^{\prime}_{1}\cup W_{1}]$ is $K_{p}$-free. If
$H[V^{\prime}_{2}\cup W_{2}]$ be $K_{q}$-free, then the proof is complete. So,
we may assume that there exists a copy $K^{\prime\prime}$ of $K_{q}$ in
$H[V^{\prime}_{2}\cup W_{2}]$. For each $v^{\prime}_{i}\in V^{\prime}_{2}$, as
$|N(v^{\prime}_{i})\cap W_{2}|\leq 2$ and $|V^{\prime}_{2}|=q-2$, it is easy
to say that there exist two members $w^{\prime}_{1},w^{\prime}_{2}$ of
$W_{2}$, such that $w^{\prime}_{1}w^{\prime}_{2}\in E(H)$ and
$V_{2}^{\prime}\subseteq N(w^{\prime}_{i})$ for $i=1,2$, that is
$V(K^{\prime\prime})=V^{\prime}_{2}\cup\\{w^{\prime}_{1},w^{\prime}_{2}\\}$.
Therefore, we have $|N(v^{\prime})\cap W_{2}|=2$ for each $v^{\prime}\in
V^{\prime}_{2}$. As any vertex of $W_{2}$ has at most $\Delta-3$ neighbors in
$K$ and $V_{2}^{\prime}\subseteq N(w^{\prime}_{i})$, then by Proposition 5,
there exist at least two members $y_{1},y_{2}$ of $V^{\prime}_{1}$, such that
$w^{\prime}_{i}y_{i}\notin E(H)$. Without loss of generality assume that
$y_{1}\neq v^{\prime}_{1}\in V^{\prime}_{1}$, where $y_{1}w^{\prime}_{1}\notin
E(H)$. Now, we set $(V^{\prime\prime}_{1},V^{\prime\prime}_{2})$ as follows.

$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})=(V^{\prime}_{1}\setminus\\{y_{1}\\})\cup\\{v_{1}\\},V(K)\setminus
V^{\prime\prime}_{1}).$

It is clear that
$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})\in\operatorname{\mathcal{F}}$,
$|V^{\prime\prime}_{1}|=p-1\geq 5$, $v^{\prime}_{1}\in V^{\prime\prime}_{1}$
and $w_{1}v^{\prime}_{1}\notin E(H)$. So, by Claim 16, it can be said that
$H[V^{\prime}_{1}\cup W_{1}]$ is $K_{p}$-free. Also, as $|N(v^{\prime})\cap
W_{2}|=2$ for each $v^{\prime}\in V^{\prime\prime}_{2}\setminus\\{y_{1}\\}$,
$w^{\prime}_{1}w^{\prime}_{2}\in E(H)$, $w^{\prime}_{1}y_{1}\notin E(H)$,
$V_{2}^{\prime\prime}\setminus\\{y_{1}\\}\subseteq N(w^{\prime}_{i})$ for
$i=1,2$, and $q\geq 6$, one can say that $H[V^{\prime\prime}_{2}\cup W_{2}]$
is $K_{q}$-free and the proof is complete. ∎

Now as $|V_{1}|=p-1$, by Claim 17 we have $H[V_{1}\cup W_{1}]$ is
$K_{p}$-free. Therfore, by the assumption that $H$ is a minimal counter-
example of Theorem 3, we can assume that there exists a copy $K^{\prime}$ of
$K_{q}$ in $H[V_{2}\cup W_{2}]$. By considering the vertices of
$V(K^{\prime})$ and as any member of $K^{\prime}$ has three adjacents in
$H^{\prime}$, one can assume that $q-3\leq|V(K^{\prime})\cap V_{2}|\leq q-2$.
First assume that $|V(K^{\prime})\cap V_{2}|=q-3$, that is there exist three
vertices $w^{\prime}_{i}$, $i=1,2,3$ of $W_{2}$, such that
$w^{\prime}_{i}w^{\prime}_{j}\in E(H)$ and $|V_{2}\cap N(w^{\prime}_{1})\cap
N(w^{\prime}_{2})\cap N(w^{\prime}_{3})|\geq|V_{2}|-1=q-3$. Without loss of
generality assume that
$V^{\prime\prime}_{2}=V_{2}\setminus\\{v^{\prime\prime}_{1}\\}\subseteq
V_{2}\cap N(w^{\prime}_{1})\cap N(w^{\prime}_{2})\cap N(w^{\prime}_{3})$. By
Claim 15, one can say that $|N(v)\cap W_{1}|=0$ for each $v\in V_{1}$. Also,
as $|V_{2}\cap N(w^{\prime}_{1})\cap N(w^{\prime}_{2})\cap
N(w^{\prime}_{3})|\geq|V_{2}|-1=q-3$ and $|V_{2}|=q-2$, then by Proposition 5,
it can be said that there exist two members $\\{v_{1},v_{2}\\}$ of $V_{1}$,
such that $v_{i}w^{\prime}_{i}\notin E(H)$. Now, we define
$(V^{\prime}_{1},V^{\prime}_{2})$ as follows.

$(V^{\prime}_{1},V^{\prime}_{2})=(V(K)\setminus
V^{\prime}_{2},V_{2}\setminus\\{v^{\prime\prime}_{1},v^{\prime\prime}_{2}\\}\cup\\{v_{1},v_{2}\\}).$

It is clear that
$(V^{\prime}_{1},V^{\prime}_{2})\in\operatorname{\mathcal{F}}$,
$|V^{\prime}_{1}|=p-1\geq 5$, and $|N(v)\cap W_{1}|=0$ for at least $p-3$
vertices of $V^{\prime}_{1}$. So, it can be said that $H[V^{\prime}_{1}\cup
W_{1}]$ is $K_{p}$-free. Also, as $q\geq 6$, and for each $v^{\prime}\in
V^{\prime}_{2}\setminus\\{v_{1},v_{2}\\}$, $|N(v^{\prime})\cap W_{2}|=3$ and
$w^{\prime}_{i}v^{\prime}\in E(H)$ for each $i=1,2,3$, also as
$v_{i}w^{\prime}_{i}\notin E(H)$, one can say that $H[V^{\prime}_{2}\cup
W_{2}]$ is $K_{q}$-free and the proof is complete. So, we may suppose that
$|V(K^{\prime})\cap V_{2}|=q-2$, that is there exist two vertices
$w^{\prime}_{i}$, $i=1,2$ of $W_{2}$, such that
$w^{\prime}_{1}w^{\prime}_{2}\in E(H)$ and $V_{2}\subseteq N(w^{\prime}_{i})$
for $i=1,2$. By Claim 15, for each $v\in V_{1}$, we have $|N(v)\cap W_{1}|\leq
1$. Also, by Proposition 5 there exist two members $\\{v_{1},v_{2}\\}$ of
$V_{1}$, such that $v_{i}w^{\prime}_{i}\notin E(H)$ for $i=1,2$. In this case,
we set $(V^{\prime}_{1},V^{\prime}_{2})$ as follows.

$(V^{\prime}_{1},V^{\prime}_{2})=(V(K)\setminus
V_{2},V_{2}\setminus\\{v^{\prime}_{1},v^{\prime}_{2}\\}\cup\\{v_{1},v_{2}\\}).$

It is clear that
$(V^{\prime}_{1},V^{\prime}_{2})\in\operatorname{\mathcal{F}}$. Also, as
$|N(v^{\prime})\cap W_{2}|\leq 3$, $w^{\prime}_{i}v^{\prime}\in E(H)$ for each
$v^{\prime}\in V^{\prime}_{2}\setminus\\{v_{1},v_{2}\\}$, and
$v_{i}w^{\prime}_{i}\notin E(H)$, one can say that $H[V^{\prime}_{2}\cup
W_{2}]$ is $K_{q}$-free. Now, assume that $H[V^{\prime}_{1}\cup W_{1}]$ has a
copy of $K_{p}$. Therefore, as $p,q\geq 6$ and by Claim 15, we have $|N(v)\cap
W_{1}|=1$ for each $v\in
V^{\prime}_{1}\setminus\\{v^{\prime}_{1},v^{\prime}_{2}\\}$. One can assume
that there exists a vertex $w_{1}$ of $W_{1}$, such that
$V^{\prime}_{1}\subseteq N(w_{1})$. Hence, we should have $|N(v)\cap W_{1}|=1$
for each $v\in V^{\prime}_{1}$ and $|N(v^{\prime})\cap W_{2}|=2$ for each
$v^{\prime}\in V^{\prime}_{2}\setminus\\{v_{1},v_{2}\\}$. As $H[V_{1}\cup
W_{1}]$ is $K_{p}$-free and $V^{\prime}_{1}\subseteq N(w_{1})$, one can assume
that $w_{1}v_{i}\notin E(H)$ for at least one $i\in\\{1,2\\}$. Without loss of
generality assume that $w_{1}v_{1}\notin E(H)$. Now, we set
$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})$ as follows.

$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})=(V_{1}\setminus\\{v_{2}\\}\cup\\{v^{\prime}_{1}\\},V(K)\setminus
V^{\prime\prime}_{1}).$

It is easy to say that
$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})\in\operatorname{\mathcal{F}}$,
$|V^{\prime\prime}_{1}|=p-1\geq 5$, $v_{1}w_{1}\notin E(H)$,
$V^{\prime\prime}_{1}\setminus\\{v_{1}\\}\subseteq N(w_{1})$, and $|N(v)\cap
W_{1}|=1$ for each $v\in V^{\prime\prime}_{1}$. So, it can be said that
$H[V^{\prime\prime}_{1}\cup W_{1}]$ is $K_{p}$-free. Also, as
$|N(v^{\prime})\cap W_{2}|=2$ for each $v^{\prime}\in
V^{\prime\prime}_{2}\setminus\\{v_{2}\\}$,
$V^{\prime\prime}_{2}\setminus\\{v_{2}\\}\subseteq N(W^{\prime}_{i})$ for
$i=1,2$, and $w^{\prime}_{2}v^{\prime}_{2}\notin E(H)$, one can say that
$H[V^{\prime}_{2}\cup W_{2}]$ is $K_{q}$-free. Hence, the proof is complete. ∎

######  Fact 18.

Theorem 3 holds for the case that $H$ is a $\Delta$-regular graph with
$\chi(H)=\Delta$, $\omega(H)=\Delta-3$, and $p\geq q\geq 7$.

###### Proof of the Fact 18.

Without loss of generality we may assume that $H$ is a minimal counter-example
of Theorem 3 where $H$ is $\Delta$-regular, $\chi(H)=\Delta$, and
$\omega(H)=\Delta-3$. Assume that $K$ be a $\Delta-3$ clique in $H$. Set
$H^{\prime}=H\setminus K$. Hence, each vertex of $K$ has four adjacents in
$H^{\prime}$ and by $\omega(H)=\Delta-3$, any vertex of $H^{\prime}$ has at
most $\Delta-4$ neighbors in $K$. Since $H$ is a minimal counter-example,
there exists a $(W_{1},W_{2})$-decomposition of $V(H^{\prime})$, such that
$H^{\prime}[W_{1}]$ is $K_{p}$-free and $H^{\prime}[W_{2}]$ is $K_{q}$-free.
Set $\operatorname{\mathcal{F}}$ as follows.

$\operatorname{\mathcal{F}}=\\{(V^{\prime},V^{\prime\prime})~{}~{}|~{}~{}V^{\prime}\cap
V^{\prime\prime}=\emptyset,~{}V^{\prime}\cup
V^{\prime\prime}=V(K),~{}p-3\leq|V^{\prime}|\leq
p-1,q-3\leq|V^{\prime\prime}|\leq q-1\\}.$

For each $(V^{\prime},V^{\prime\prime})\in\operatorname{\mathcal{F}}$, it can
be said that $H[V^{\prime}]$ is $K_{p}$-free and $H[V^{\prime\prime}]$ is
$K_{q}$-free. For each $i\in[|\operatorname{\mathcal{F}}|]$, define
$e=|E(H[W_{1},V^{\prime}])|+|E(H[W_{2},V^{\prime\prime}])|$, where
$(V^{\prime},V^{\prime\prime})$ is a member of $\operatorname{\mathcal{F}}$.
Without loss of generality we may suppose that
$e_{1}=|E(H[W_{1},V_{1}])|+|E(H[W_{2},V_{1}^{\prime}])|\leq|E(H[W_{1},V_{i}])|+|E(H[W_{2},V_{i}^{\prime}])|$
for each $(V_{i},V_{i}^{\prime})\in\operatorname{\mathcal{F}}$. Now, we have
the following claims.

######  Claim 19.

If there exists a vertex $v$ of $V_{1}(V^{\prime}_{1})$, such that $|N(v)\cap
W_{1}(W_{2})|\geq 3$, then for each $v^{\prime}\in V^{\prime}_{1}(V_{1})$, we
have $|N(v^{\prime})\cap W_{2}(W_{1})|\leq 1$. If $|N(v)\cap W_{1}(W_{2})|\geq
2$, then for each $v^{\prime}\in V^{\prime}_{1}(V_{1})$, we have
$|N(v^{\prime})\cap W_{2}(W_{1})|\leq 2$. Also, if there exists a vertex $v$
of $V_{1}(V^{\prime}_{1})$, such that $|N(v)\cap W_{1}(W_{2})|=4$, then for
each $v^{\prime}\in V^{\prime}_{1}(V_{1})$, we have $|N(v^{\prime})\cap
W_{2}(W_{1})|=0$.

###### Proof of Claim 19.

Without loss of generality one can assume that $|N(v)\cap W_{1}|=3$ for some
$v\in V_{1}$. Also, on contrary, suppose that there exists a vertex
$v^{\prime}$ of $V_{1}^{\prime}$, such that $|N(v^{\prime})\cap W_{2}|\geq 2$.
In this case, one can check that
$(V_{2},V_{2}^{\prime})=(V_{1}\setminus\\{v\\}\cup\\{v^{\prime}\\},V^{\prime}_{1}\setminus\\{v^{\prime}\\}\cup\\{v\\})\in\operatorname{\mathcal{F}}$.
Also, as each vertex of $K$ has four adjacents in $H^{\prime}$, then it can be
said that $e_{2}=|E(H[W_{1},V_{2}])|+|E(H[W_{2},V_{2}^{\prime}])|\leq
e_{1}-2$, which is a contradiction to the minimality of $e_{1}$. For othar
cases the proof is the same and the proof of the claim is complete. ∎

######  Claim 20.

If $|V_{1}|\geq p-2(~{}or~{}|V_{2}|\geq q-2)$, then for each vertex $v$ of
$V_{1}(V_{2})$, we have $|N(v)\cap W_{1}(W_{2})|\leq 2$.

###### Proof of Claim 20.

Without loss of generality assume that $|V_{1}|\geq p-2$, $v\in V_{1}$, and
$|N(v)\cap W_{1}|\geq 3$. Now, set
$(V_{2},V_{2}^{\prime})=(V_{1}\setminus\\{v\\},V^{\prime}_{1}\cup\\{v\\})\in\operatorname{\mathcal{F}}$.
As, each vertex of $K$ has four adjacents in $H^{\prime}$, it is easy to say
that $|N(v)\cap W_{2}|\leq 1$, which means that
$e_{2}=|E(H[W_{1},V_{2}])|+|E(H[W_{2},V_{2}^{\prime}])|\leq e_{1}-2$, which
contradicts the minimality of $e_{1}$ and the proof is complete. ∎

Now, considr $|V_{1}|$ and $|V_{2}|$. Without loss of generality assume that
$|V_{1}|\geq|V_{2}|$. Hence, we have two cases as follows.

Case 1: $|V_{1}|=p-2$ and $|V_{2}|=q-2$. In this case, by Claim 20, for each
$v\in V_{1}(V_{2})$ we have $|N(v)\cap W_{1}(W_{2})|\leq 2$. Now, by the
assumption that $H$ is a minimal counter-example of Theorem 3, we can assume
that there exists a copy of $K_{p}$ in $H[V_{1}\cup W_{1}]$ or there exists a
copy of $K_{q}$ in $H[V_{2}\cup W_{2}]$. Without loss of generality we may
assume that there exists a copy $K^{\prime}$ of $K_{p}$ in $H[V_{1}\cup
W_{1}]$. Therefore, by using Claims 19 and 20 and the fact that $|V_{1}|=p-2$,
there should be two members $w_{1}$ and $w_{2}$ of $W_{1}$, such that
$V_{1}\subseteq N(w_{i})$ and $w_{1}w_{2}\in E(H)$. Therefore, by Proposition
5, there exist two members $v^{\prime}_{1},v^{\prime}_{2}$ of $V_{2}$, such
that $w_{i}v^{\prime}_{i}\notin E(H)$. Now, we set
$(V^{\prime}_{1},V^{\prime}_{2})$ as follows.

$(V^{\prime}_{1},V^{\prime}_{2})=(V_{1}\setminus\\{v_{1},v_{2}\\})\cup\\{v^{\prime}_{1},v^{\prime}_{2}\\},V(K)\setminus
V^{\prime}_{1}).$

It is clear that
$(V^{\prime}_{1},V^{\prime}_{2})\in\operatorname{\mathcal{F}}$ and
$|V^{\prime}_{1}|=p-2\geq 5$. As $w_{i}v^{\prime}_{i}\notin E(H)$, by Claim
20, it can be said that $H[V^{\prime}_{1}\cup W_{1}]$ is $K_{p}$-free. If
$H[V^{\prime}_{2}\cup W_{2}]$ be $K_{q}$-free, then the proof is complete. So,
we may assume that there exists a copy $K^{\prime\prime}$ of $K_{q}$ in
$H[V^{\prime}_{2}\cup W_{2}]$. As $|V^{\prime}_{2}|=q-2$ and
$|N(v^{\prime}_{i})\cap W_{2}|\leq 2$ for each $v^{\prime}_{i}\in
V^{\prime}_{2}$, it is easy to say that there exist two members
$w^{\prime}_{1},w^{\prime}_{2}$ of $W_{2}$, such that
$w^{\prime}_{1}w^{\prime}_{2}\in E(H)$ and $V_{2}^{\prime}\subseteq
N(w^{\prime}_{i})$ for $i=1,2$, that is
$V(K^{\prime\prime})=V^{\prime}_{2}\cup\\{w^{\prime}_{1},w^{\prime}_{2}\\}$.
Since $w^{\prime}_{1}w^{\prime}_{2}\in E(H)$ and $V_{2}^{\prime}\subseteq
N(w^{\prime}_{i})$ for $i=1,2$, by Proposition 5 there exist at least two
members $y_{1},y_{2}$ of $V^{\prime}_{1}$, such that
$w^{\prime}_{i}y_{i}\notin E(H)$. Without loss of generality assume that
$y_{1}\neq v^{\prime}_{1}\in V^{\prime}_{1}$, where $y_{1}w^{\prime}_{1}\notin
E(H)$. Now, we set $(V^{\prime\prime}_{1},V^{\prime\prime}_{2})$ as follows.

$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})=(V^{\prime}_{1}\setminus\\{y_{1}\\})\cup\\{v_{1}\\},V(K)\setminus
V^{\prime\prime}_{1}).$

It is clear that
$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})\in\operatorname{\mathcal{F}}$.
Also, as $|V^{\prime\prime}_{1}|=p-2\geq 5$, $w_{1}v^{\prime}_{1}\notin E(H)$,
and $|N(v^{\prime})\cap W_{1}|=2$ for each $v^{\prime}_{i}\in
V^{\prime\prime}_{1}\setminus\\{v^{\prime}_{1}\\}$ and
$V_{1}^{\prime\prime}\setminus\\{v^{\prime}_{1}\\}\subseteq N(w_{i})$ for
$i=1,2$, it can be said that $H[V^{\prime\prime}_{1}\cup W_{1}]$ is
$K_{p}$-free. Since $|N(v^{\prime})\cap W_{2}|=2$ for each $v^{\prime}\in
V^{\prime\prime}_{2}$, $w^{\prime}_{1}w^{\prime}_{2}\in E(H)$, and
$V_{2}^{\prime\prime}\setminus\\{y_{1}\\}\subseteq N(w^{\prime}_{i})$ for
$i=1,2$, one can say that $H[V^{\prime\prime}_{2}\cup W_{2}]$ is $K_{q}$-free
and the proof is complete.

Case 2: $|V_{1}|=p-1$ and $|V_{2}|=q-3$. In this case, by Claim 20, one can
say that $|N(v)\cap W_{1}|\leq 2$ for each $v\in V_{1}$. If there exists a
member $v$ of $V_{1}$, such that $|N(v)\cap W_{1}|=2$, then $|N(v)\cap
W_{2}|=2$. Otherwise, we come to a contradiction by the minimality of $e_{1}$
by considring
$(V^{\prime}_{1},V^{\prime}_{2})=(V_{1}\setminus\\{v\\},V(K)\setminus
V^{\prime}_{1})$. So, assume that $|N(v)\cap W_{1}|=2$ and set
$(V^{\prime}_{1},V^{\prime}_{2})=(V_{1}\setminus\\{v\\},V(K)\setminus
V^{\prime}_{1})$. One can say that
$(V^{\prime}_{1},V^{\prime}_{2})\in\operatorname{\mathcal{F}}$ and
$e=e_{1}=|E(H[W_{1},V_{1}])|+|E(H[W_{2},V_{2}])|=e^{\prime}=|E(H[W_{1},V^{\prime}_{1}])|+|E(H[W_{2},V_{2}^{\prime}])|$,
therefore the proof is complete by Case 1. Hence, we may suppose that
$|N(v)\cap W_{1}|\leq 1$ for each $v\in V_{1}$. Now, by assumption that $H$ is
a minimal counter-example of Theorem 3, we can assume that there exists a copy
of $K_{p}$ in $H[V_{1}\cup W_{1}]$ or there exists a copy of $K_{q}$ in
$H[V_{2}\cup W_{2}]$. First, we may assume that there exists a copy
$K^{\prime}$ of $K_{p}$ in $H[V_{1}\cup W_{1}]$. Therefore, as $|V_{1}|=p-1$
and $|N(v)\cap W_{1}|\leq 1$ for each $v\in V_{1}$, there exiasts a member
$w_{1}$ of $W_{1}$, such that $V_{1}\subseteq N(w_{1})$. Therefore, by
Proposation 5 there exists a member $v^{\prime}_{1}$ of $V_{2}$, such that
$w_{1}v^{\prime}_{1}\notin E(H)$. Now, we set
$(V^{\prime}_{1},V^{\prime}_{2})$ as follows.

$(V^{\prime}_{1},V^{\prime}_{2})=(V_{1}\setminus\\{v_{1}\\})\cup\\{v^{\prime}_{1}\\},V(K)\setminus
V^{\prime}_{1}).$

It is clear that
$(V^{\prime}_{1},V^{\prime}_{2})\in\operatorname{\mathcal{F}}$ and
$|V^{\prime}_{1}|=p-1\geq 6$. As $w_{1}v^{\prime}_{1}\notin E(H)$ and
$|N(v)\cap W_{1}|\leq 1$ for each $v\in V_{1}$, it can be said that
$H[V^{\prime}_{1}\cup W_{1}]$ is $K_{p}$-free. If $H[V^{\prime}_{2}\cup
W_{2}]$ is $K_{q}$-free, then the proof is complete. So, we may assume that
there exists a copy $K^{\prime\prime}$ of $K_{q}$ in $H[V^{\prime}_{2}\cup
W_{2}]$. As $|N(v_{i})\cap W_{2}|\leq 3$ and $|V^{\prime}_{2}|=q-3$, it is
easy to say that there exist three members
$w^{\prime}_{1},w^{\prime}_{2},w^{\prime}_{3}$ of $W_{2}$, such that
$w^{\prime}_{i}w^{\prime}_{j}\in E(H)$ and $V_{2}^{\prime}\subseteq
N(w^{\prime}_{i})$ for $i=1,2,3$, that is
$V(K^{\prime\prime})=V^{\prime}_{2}\cup\\{w^{\prime}_{1},w^{\prime}_{2},w^{\prime}_{3}\\}$.
Now, one can say that there exists at least one member $y_{1}\neq
v^{\prime}_{1}$ of $V^{\prime}_{1}$, such that $w^{\prime}_{i}y_{1}\notin
E(H)$ for one $i\in\\{1,2,3\\}$. Assume that $y_{1}w^{\prime}_{1}\notin E(H)$.
Now, we set $(V^{\prime\prime}_{1},V^{\prime\prime}_{2})$ as follows.

$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})=(V^{\prime}_{1}\setminus\\{y_{1}\\})\cup\\{v_{1}\\},V(K)\setminus
V^{\prime\prime}_{1}).$

It is clear that
$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})\in\operatorname{\mathcal{F}}$,
$|V^{\prime\prime}_{1}|=p-1\geq 6$, and $w_{1}v^{\prime}_{1}\notin E(H)$. So,
it can be said that $H[V^{\prime\prime}_{1}\cup W_{1}]$ is $K_{p}$-free. Also,
as $|N(v^{\prime})\cap W_{2}|=3$ for each $v^{\prime}\in V^{\prime}_{2}$,
$w^{\prime}_{1}w^{\prime}_{2}\in E(H)$, and
$V_{2}^{\prime\prime}\setminus\\{y_{1}\\}\subseteq N(w^{\prime}_{i})$ for
$i=1,2,3$ and $y_{1}w^{\prime}_{1}\notin E(H)$, one can say that
$H[V^{\prime\prime}_{2}\cup W_{2}]$ is $K_{q}$-free and the proof is complete.

Now, we may assume that $H[V_{1}\cup W_{1}]$ is $K_{p}$-free, and there exists
a copy of $K_{q}$ in $H[V_{2}\cup W_{2}]$. Without loss of generality we may
assume that $K^{\prime}=K_{q}\subseteq H[V_{2}\cup W_{2}]$. By considering the
vertices of $V(K^{\prime})$ and as each vertex of $K$ has four adjacents in
$H^{\prime}$, one can assume that $q-4\leq|V(K^{\prime})\cap V_{2}|\leq q-3$.
Let $|V(K^{\prime})\cap V_{2}|=q-4$, that is there exist four vertices
$w^{\prime}_{i}$, $i=1,2,3,4$ of $W_{2}$, such that
$w^{\prime}_{i}w^{\prime}_{j}\in E(H)$ and $|V_{2}\cap N(w^{\prime}_{1})\cap
N(w^{\prime}_{2})\cap N(w^{\prime}_{3})|\geq q-4$. By Claim 19, for each $v\in
V_{1}$, we have $|N(v)\cap W_{1}|=0$. Assume that
$\\{v^{\prime}_{1},v_{2}^{\prime},v^{\prime}_{3}\\}\subseteq V_{2}\cap
N(w^{\prime}_{1})\cap N(w^{\prime}_{2})\cap N(w^{\prime}_{3})$. Also, by
Proposition 5 there exist three members $\\{v_{1},v_{2},v_{3}\\}$ of $V(K)$,
such that $v_{i}w^{\prime}_{i}\notin E(H)$. Now, we set
$(V^{\prime}_{1},V^{\prime}_{2})$ as follows.

$(V^{\prime}_{1},V^{\prime}_{2})=(V(K)\setminus
V^{\prime}_{2},V_{2}\setminus\\{v^{\prime}_{1},v_{2}^{\prime},v^{\prime}_{3}\\}\cup\\{v_{1},v_{2},v_{3}\\}).$

It is clear that
$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})\in\operatorname{\mathcal{F}}$,
$|V^{\prime}_{1}|=p-1\geq 6$, and $|N(v)\cap W_{1}|=0$ for at least five
vertices of $V^{\prime}_{1}$. Hence, it can be said that $H[V^{\prime}_{1}\cup
W_{1}]$ is $K_{p}$-free. Also, as $|N(v^{\prime})\cap W_{2}|=4$,
$w^{\prime}_{i}v^{\prime}\in E(H)$ for each $v^{\prime}\in
V^{\prime}_{2}\setminus\\{v_{1},v_{2},v_{3}\\}$, and
$v_{i}w^{\prime}_{i}\notin E(H)$, one can say that $H[V^{\prime}_{2}\cup
W_{2}]$ is $K_{q}$-free and the proof is complete. So, we may suppose that
$|V(K^{\prime})\cap V_{2}=V_{2}|=q-3$, that is there exist three vertices
$w^{\prime}_{i}$, $i=1,2,3$ of $W_{2}$, such that
$w^{\prime}_{i}w^{\prime}_{j}\in E(H)$ and $V_{2}\subseteq N(w^{\prime}_{i})$.
By Claim 19, for each $v\in V_{1}$, we have $|N(v)\cap W_{1}|\leq 1$ and by
Proposition 5, there exist three members $\\{v_{1},v_{2},v_{3}\\}$ of $V(K)$,
such that $v_{i}w^{\prime}_{i}\notin E(H)$. Now, we set
$(V^{\prime}_{1},V^{\prime}_{2})$ as follows.

$(V^{\prime}_{1},V^{\prime}_{2})=(V(K)\setminus
V^{\prime}_{2},V_{2}\setminus\\{v^{\prime}_{1},v^{\prime}_{2},v^{\prime}_{3}\\}\cup\\{v_{1},v_{2},v_{3}\\}).$

It is clear that
$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})\in\operatorname{\mathcal{F}}$. As
$q\geq 7$, $|N(v^{\prime})\cap W_{2}|\leq 4$, $w^{\prime}_{i}v^{\prime}\in
E(H)$ for each $v^{\prime}\in V^{\prime}_{2}\setminus\\{v_{1},v_{2},v_{3}\\}$,
and $v_{i}w^{\prime}_{i}\notin E(H)$, one can say that $H[V^{\prime}_{2}\cup
W_{2}]$ is $K_{q}$-free. Now, assume that $H[V^{\prime}_{1}\cup W_{1}]$ has a
copy of $K_{p}$. Therefore, as $p\geq 7$ and for each $v\in V_{1}$ we have
$|N(v)\cap W_{1}|\leq 1$, one can assume that there exists a vertex $w_{1}$ of
$W_{1}$, such that $V^{\prime}_{1}\subseteq N(w_{1})$. Hence, we should have
$|N(v)\cap W_{1}|=1$ for each $v\in V^{\prime}_{1}$ and $|N(v^{\prime})\cap
W_{2}|\leq 3$ for each $v^{\prime}\in V^{\prime}_{2}$. As $H[V_{1}\cup W_{1}]$
is $K_{p}$-free and $V^{\prime}_{1}\subseteq N(w_{1})$, one can assume that
$w_{1}v_{i}\notin E(H)$ for at least one $i\in\\{1,2,3\\}$. Without loss of
generality we may assume that $w_{1}v_{1}\notin E(H)$. Now, we set
$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})$ as follows.

$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})=(V_{1}\setminus\\{v_{2},v_{3}\\}\cup\\{v^{\prime}_{1},v^{\prime}_{2}\\},V(K)\setminus
V^{\prime\prime}_{1}).$

It is clear that
$(V^{\prime\prime}_{1},V^{\prime\prime}_{2})\in\operatorname{\mathcal{F}}$ and
$|V^{\prime}_{1}|=p-1\geq 6$. As $v_{1}w_{1}\notin E(H)$,
$V^{\prime\prime}_{1}\setminus\\{v_{1}\\}\subseteq N(w_{1})$, and $|N(v)\cap
W_{1}|=1$ for each $v\in V^{\prime\prime}_{1}$, and
$|V^{\prime\prime}_{1}|=p-1\geq 6$, it can be said that
$H[V^{\prime\prime}_{1}\cup W_{1}]$ is $K_{p}$-free. Also, as
$|N(v^{\prime})\cap W_{2}|\leq 3$ for each $v^{\prime}\in
V^{\prime\prime}_{2}$, and $w^{\prime}_{i}v^{\prime}_{i}\notin E(H)$ for
$i=2,3$, one can say that $H[V^{\prime}_{2}\cup W_{2}]$ is $K_{q}$-free.
Therfore the proof is complete. ∎

By Fact 10, Fact 13 , Fact 14, and Fact 18, we prove that Theorem 3 is true
for some cases. To prove another cases we need the following results of Landon
Rabern.

######  Theorem 21.

[12] If $H$ is a graph with $\omega(H)\geq\frac{3(\Delta+1)}{4}$, then $H$ has
an independent set $I$ such that $\omega(H\setminus I)\leq\omega(H)-1$.

######  Theorem 22.

[9] If $H$ is a connected graph with $\omega(H)>\frac{2(\Delta+1)}{3}$, then
$H$ has an independent set $I$ such that $\omega(H\setminus
I)\leq\omega(H)-1$, unless it is the strong product of an odd cycle with
length at least $5$ and the complete graph $K_{\frac{\omega(H)}{2}}$.

In the following, we prove Theorem 3.

######  Proof of Theorem 3.

Without loss of generality we may assume that $p\geq q$. If
$\chi(H)\leq\Delta-1$ then the proof is trivial. So, assume that
$\chi(H)=\Delta$. Therefore, by Theorem 4 we should have
$\Delta-3\leq\omega(H)\leq\Delta-1$. When $\omega(H)=\Delta-1$, by Fact 10,
the proof is complete for each $p,q\geq 5$. When $\omega(H)=\Delta-2$, by Fact
14, the proof is complete for each $p,q\geq 6$, and for $q=2$ the proof is
trivial. Also, when $\omega(H)=\Delta-3$, by Fact 18, the proof is complete
for each $p,q\geq 7$, and for $q\leq 3$ the proof is trivial. Therefore, we
need to show that the theorem holds for the following cases:

  * •

$\omega(H)=\Delta-1$ and $q\in\\{2,3,4\\}$,

  * •

$\omega(H)=\Delta-2$ and $q\in\\{3,4,5\\}$,

  * •

$\omega(H)=\Delta-3$ and $q\in\\{4,5,6\\}$.

Case 1: Assume that $\omega(H)=\Delta-1$ and $q\in\\{2,3,4\\}$. In this case
we have $(p,q)\in\\{(\Delta-1,2),(\Delta-2,3),(\Delta-3,4)\\}$. First assume
that $(p,q)=(\Delta-1,2)$. By Theorem 21, one can say that $H$ has a
independent set $I_{1}$, such that $\omega(H\setminus I_{1})\leq\Delta-2$. By
setting $(V_{1},V_{2})=(V(H)\setminus I_{1},I_{1})$, the proof is complete.
Now assume that $(p,q)=(\Delta-2,3)$. Let $I_{1}$ be a maximum independent set
of $H$. Therefore, we have $\Delta(H\setminus I_{1})\leq\Delta-1$. If
$\omega(H\setminus I_{1})\leq\Delta-3$, the proof is complete. So, assume that
$\omega(H\setminus I_{1})=\Delta-2$. Therefore as $\Delta\geq 13$, by Theorem
21, $H\setminus I_{1}$ has a independent set $I_{2}$, such that
$\omega(H\setminus I_{1})\leq\Delta-3$. By setting
$(V_{1},V_{2})=(V(H)\setminus(I_{1}\cup I_{2}),I_{1}\cup I_{2})$, the proof is
complete. For the case that $(p,q)=(\Delta-3,4)$ the proof is the same.

Case 2: Assume that $\omega(H)=\Delta-2$ and $q\in\\{3,4,5\\}$. In this case
we have $(p,q)\in\\{(\Delta-2,3),(\Delta-3,4),(\Delta-4,5)\\}$. For
$(p,q)=(\Delta-2,3)$ the proof is complete by Case 1. Now assume that
$(p,q)=(\Delta-3,4)$, for other case the proof is same. Let $I_{1}$ be a
maximum independent set of $H$ and $I_{2}$ be a maximum independent set of
$H\setminus I_{1}$ . Therefore, we have $\Delta(H\setminus(I_{1}\cup
I_{2}))\leq\Delta-2$. If $\omega(H\setminus(I_{1}\cup I_{2}))\leq\Delta-4$,
the proof is complete. So, assume that $\omega(H\setminus(I_{1}\cup
I_{2}))=\Delta-3$. Therefore as $\Delta\geq 13$ and
$\Delta(H\setminus(I_{1}\cup I_{2}))\leq\Delta-2$, by Theorem 21 and Theorem
22, one can say that $H\setminus(I_{1}\cup I_{2})$ has a independent set
$I_{3}$, such that $\omega(H\setminus(I_{1}\cup I_{2}))\leq\Delta-4$. By
setting $(V_{1},V_{2})=(V(H)\setminus(I_{1}\cup I_{2}\cup I_{3}),I_{1}\cup
I_{2}\cup I_{3})$, the proof is complete.

Case 3: Assume that $\omega(H)=\Delta-3$ and $q\in\\{4,5,6\\}$. Therefore,
consider the case that $\omega(H)=\Delta-3$ and
$(p,q)\in\\{(\Delta-3,4),(\Delta-4,5),(\Delta-5,6)\\}$. First assume that
$(p,q)=(\Delta-3,4)$. Let $I_{1}$ be a maximum independent set of $H$.
Therefore, we have $\Delta(H\setminus I_{1})\leq\Delta-1$. If
$\omega(H\setminus I_{1})\leq\Delta-4$, the proof is complete. So, assume that
$\omega(H\setminus I_{1})=\Delta-3$. Hence as $\Delta\geq 13$, by Theorem 21
one can say that $H\setminus I_{1}$ has a independent set $I_{2}$, such that
$\omega(H\setminus I_{1})\leq\Delta-4$. By setting
$(V_{1},V_{2})=(V(H)\setminus(I_{1}\cup I_{2}),I_{1}\cup I_{2})$, the proof is
complete. Now, assume that $(p,q)=(\Delta-4,5)$. For $(p,q)=(\Delta-5,6)$ the
proof is the same. Let $I_{1}$ is a maximum independent set of $H$. Therefore,
$\Delta(H\setminus I_{1})\leq\Delta-1$. Assume that $\omega(H\setminus
I_{1})\leq\Delta-4$, and set $I_{2}$ is a maximum independent set of
$H\setminus I_{1}$. Therefore, $\Delta(H\setminus(I_{1}\cup
I_{2}))\leq\Delta-2$. If $\omega(H\setminus(I_{1}\cup I_{2}))\leq\Delta-5$,
the proof is complete. So, assume that $\omega(H\setminus(I_{1}\cup
I_{2}))=\Delta-4$. Now, as $\Delta(H\setminus(I_{1}\cup I_{2}))\leq\Delta-2$
and $\Delta\geq 13$, so by Theorem 22, one can say that $H\setminus(I_{1}\cup
I_{2})$ has a independent set $I_{3}$, such that $\omega(H\setminus(I_{1}\cup
I_{2}\cup I_{3}))\leq\Delta-5$. By setting
$(V_{1},V_{2})=(V(H)\setminus(I_{1}\cup I_{2}\cup I_{3}),I_{1}\cup I_{2}\cup
I_{3})$ the proof is complete. Therfore, we may assume that $\omega(H\setminus
I_{1})=\Delta-3$. So by Theorem 21, $H\setminus I_{1}$ has a independent set
$I_{2}$, such that $\omega(H\setminus(I_{1}\cup I_{2}))\leq\Delta-4$.
Therefore, $\Delta(H\setminus(I_{1}\cup I_{2}))\leq\Delta-2$. If
$\omega(H\setminus(I_{1}\cup I_{2}))\leq\Delta-5$, the proof is complete. So,
assume that $\omega(H\setminus(I_{1}\cup I_{2}))=\Delta-4$. So as
$\Delta(H\setminus(I_{1}\cup I_{2}))\leq\Delta-2$ and $\Delta\geq 13$, by
Theorem 22 one can checked that $H\setminus(I_{1}\cup I_{2})$ has a
independent set $I_{3}$, such that $\omega(H\setminus(I_{1}\cup I_{2}\cup
I_{3}))\leq\Delta-5$. By setting $(V_{1},V_{2})=((V(H)\setminus(I_{1}\cup
I_{2}\cup I_{3})),I_{1}\cup I_{2}\cup I_{3})$ the proof is complete.

Hence, by Case 1, Case 2, and Case 3 the theorem holds. ∎

##  3\. Proof of Theorem 1 and Theorem 2

In this section, we prove the main results.

######  Proof of Theorem 1.

First note that we only need to prove the statement for $k=2$. By Theorem 3
one can said that the statement holds for $k=2$. To prove Theorem 1, set
$p=\sum_{i=1}^{k-1}p_{i}-(k-2)$ and $q=p_{k}$. Hence $p+q=\Delta(H)+1$. Since
the statement is true for $k=2$, we have a partition of $V(H)$ into
$(V_{1},V_{2})$ such that $H[V_{1}]$ is $K_{p}$-free and $H[V_{2}]$ is
$K_{q}$-free. Also, assume that $V_{2}$ is a maximall $K_{q}$-free subset of
$H$, such that for which we have $H[V_{1}]$ is $K_{p}$-free. Therefore, each
vertex in $V_{1}$ has at least $q-1$ neighbours in $V_{2}$. Thus, the maximum
degree of $H[V_{1}]$ is at most $\Delta(H)-(q-1)=p$.

If the maximum degree of $H[V_{1}]$ is less than $p$, let $v\in V_{1}$ be a
vertex with maximum degree in $H[V_{1}]$ such that its degree is equal to
$m<p$. We add $\\{x_{1},\ldots,x_{p-m}\\}$ new vertices to $H[V_{1}]$ and join
all of them to $v$, forming a new graph $G$. The graph $G$ has maximum degree
$p$. Also it can be say that $G$ is $K_{p}$-free graph. Therefore by induction
$G$ is a $(V_{1},\ldots,V_{k-1})$-partitionable graph. Hence, there exists a
partition of $V(G)$ into $V^{\prime}_{1},\cdots,V^{\prime}_{k-1}$ such that
for each $1\leq i\leq k-1$, $G[V^{\prime}_{i}]$ is $K_{p_{i}}$-free. Therefore
it can be say that $V^{\prime}_{1}\cap V_{1},\ldots,V^{\prime}_{k-1}\cap
V_{1},V_{2}$ is the desired partition of $V(H)$, that is $H$ is a
$(V_{1},\ldots,V_{k})$-partitionable graph. Therefore, we may assume that
$H[V_{1}]$ is a graph with maximum degree $p$. We also have
$\omega(H[V_{1}])\leq p-1$, $p_{1}+p_{2}\geq 14$, and
$\sum_{i=1}^{k-1}p_{i}=\Delta(H[V_{1}])-1+(k-1)$. We iterate this procedure
until we obtain the desired partition.

As $k\geq 3$ and $p_{1}+p_{2}\geq 14$, we can assume that $H[V_{1}]$ has
maximum degree $p\geq 13$. Now, we have $\sum_{i=1}^{k-1}p_{i}=p-1+(k-1)$. We
iterate this procedure until to obtain the required partition. Hence, the
proof is complete. ∎

######  Proof of Theorem 2.

First note that we only need to prove the statement for $k=2$. Assume that the
statement holds for $k=2$, i.e. if $\Delta(H)-3\leq\omega(H)\leq\Delta(H)-1$,
$p,q\geq 2$, and $p+q=\Delta(H)+1\geq 14$, then there exists a partition of
$V(H)$ into $(V_{1},V_{2})$ such that $H[V_{1}]$ is a maximum $K_{p}$-free
subgraph and $H[V_{2}]$ is $K_{q}$-free. To prove Theorem 2, set
$q=\sum_{i=2}^{k}p_{i}-(k-2)$ and $p=p_{1}$. Since the statement is true for
$k=2$, we have a partition of $V(H)$ into $(V_{1},V_{2})$ such that $H[V_{1}]$
is a maximum $K_{p}$-free subgraph and $H[V_{2}]$ is $K_{q}$-free. As
$H[V_{1}]$ is a maximum $K_{p}$-free subgraph, each vertex in $V_{2}$ has at
least $p-1$ neighbours in $V_{1}$. Thus, the maximum degree of $H[V_{2}]$ is
at most $\Delta(H)-(p-1)=q$. We can assume that $H[V_{2}]$ has maximum degree
$q\geq 13$. Now, we have $\sum_{i=2}^{k}p_{i}=p-1+(k-1)$. We iterate this
procedure until to obtain the required partition.

Now, we prove the statement for $k=2$. Without loss of generality we may
assume that $p\geq q$. On contrary, we may suppose that $H$ is a minimal
counter-example of Theorem 2 with maximum degree $\Delta$ and $\omega(H)=t$,
where $t\in\\{\Delta-3,\Delta-2,\Delta-1\\}$. Let $K$ is a $t$ clique in $H$.
Set $H^{\prime}=H\setminus K$. Since each vertex of $K$ has at most theree
adjacents in $H^{\prime}$ and for each $v\in M$ and as any vertex of
$H^{\prime}$ has at most $t-1$ neighbors in $K$, then one can assume that
$\Delta(H)-t+1\leq\Delta(H^{\prime})\leq\Delta(H)$. If the maximum degree of
$H^{\prime}$ is less than $\Delta(H)$, let $v\in V(H^{\prime})$ be a vertex
with maximum degree in $H^{\prime}$ such that its degree is equal to
$m<\Delta(H)$. We add $X^{\prime}=\\{x_{1},\ldots,x_{m}\\}$ new vertices to
$H^{\prime}$ and join all of them to $v$, forming a new graph $G$, where
$m\leq t-1$ and $m+\Delta(H^{\prime})=\Delta(H)$. The graph $G$ has maximum
degree $\Delta(H)$. Also it can be say that $|V(G)|\leq|V(H)|-1$ and
$\omega(G)\leq\Delta(G)-1$.

Since $H$ is a minimal counter-example, there exists a
$(W_{1},W_{2})$-decomposition of $V(G)$, such that $G[W_{1}]$ is a maximum
$K_{p}$-free subgraph and $G[W_{2}]$ is $K_{q}$-free. Assume that
$(Y_{1},Y_{2})=(W_{1}\cap V(H^{\prime}),W_{2}\cap V(H^{\prime})$. As
$G[X^{\prime}]$ is independent, it easy to say that $(Y_{1},Y_{2})$ is a
decomposition of $V(H^{\prime})$, such that in $H^{\prime}$,
$H^{\prime}[Y_{1}]$ is a maximum $K_{p}$-free subgraph and $H^{\prime}[Y_{2}]$
is $K_{q}$-free.

Now, consider $(S_{1},S_{2})$-decomposition of $V(H)$, such that
$S_{1}=Y_{1}\cup V_{1}$ and $S_{2}=Y_{2}\cup V_{2}$ where
$|V_{1}|=p-1,|V_{2}|=t-p+1$, and $V_{1}\cup V_{2}=V(K)$. By Theorem 3, one can
assume that $H[S_{1}]$ is $K_{p}$-free and $H[S_{2}]$ is $K_{q}$-free. We
claim that $H[S_{1}]$ is a maximum $K_{p}$-free subgraph of $H$. Otherwise,
assume that there exists a subset $S$ of $V(H)$ with $|S|\geq|S_{1}|+1$, such
that $H[S]$ is a $K_{p}$-free subgraph and $H[V(H)\setminus S]$ is
$K_{q}$-free. As $|K|=t$ and $H[S]$ is a $K_{p}$-free, it can be said that
$|S\cap V(K)|\leq p-1$, and $t-p+1\leq|(V(H)\setminus S)\cap V(K)|\leq q-1$.
Therefore, one can say that there exists a
$(Y^{\prime}_{1},Y^{\prime}_{2})$-decomposition of $V(H^{\prime})$, such that
$H^{\prime}[Y^{\prime}_{1}]$ is $K_{p}$-free, $H^{\prime}[Y^{\prime}_{2}]$ is
$K_{q}$-free, and $|Y^{\prime}_{1}|\geq|Y_{1}|+1$, consequently there exists a
$(W^{\prime}_{1},W^{\prime}_{2})$-decomposition of $V(G)$, such that
$G[W^{\prime}_{1}]$ is $K_{p}$-free, $G[W^{\prime}_{2}]$ is $K_{q}$-free, and
$|W^{\prime}_{1}|\geq|W_{1}|+1$, were
$(W^{\prime}_{1},W^{\prime}_{2})=(Y^{\prime}_{1}\cup
X^{\prime},Y^{\prime}_{2})$, which contradicts the fact that $G[W_{1}]$ is a
maximum $K_{p}$-free subgraph of $G$. Therefore, $H[S_{1}]$ is a maximum
$K_{p}$-free subgraph of $H$ and that the proof is complete. ∎

###  3.1.  Some research problems related to the contents of this paper.

In this section, we propose some research problems related to the contents of
this paper. The first problem concerns Theorem 3, Theorem 2 and Theorem A, as
we address below.

######  Problem 22.1.

Let $p$ and $q$ are two positive integers, where $p,q\geq 2$ and
$p+q=\Delta+1$. Suppose that $H$ is a graph with $\Delta(H)=\Delta\leq 12$ and
$\omega(H)\leq\Delta-1$. If $\Delta+1=p+q$, then there exists a
$(V_{1},V_{2})$-decomposition of $V(H)$, so that $H[V_{1}]$ is a $K_{p}$-free
subgraph and $H[V_{2}]$ is a $K_{q}$-free subgraph of $H$.

######  Problem 22.2.

Let $p$ and $q$ are two positive integers, where $p,q\geq 3$ and
$p+q=\Delta+1$. Suppose that $H$ is a graph with $\Delta(H)=\Delta\geq 5$ and
$\omega(H)\leq\Delta-1$. There exists a $(V_{1},V_{2})$-decomposition of
$V(H)$, so that $H[V_{1}]$ is a maximum $K_{p}$-free subgraph and $H[V_{2}]$
is a $K_{q}$-free subgraph of $H$.

######  Problem 22.3.

Let $p$ and $q$ are two positive integers, where $p,q\geq 3$ and
$p+q=\Delta+1$. Suppose that $H$ is a graph with $\Delta(H)=\Delta\geq 5$ and
$\omega(H)\leq\Delta-1$. There exists a $(V_{1},V_{2})$-decomposition of
$V(H)$, so that $H[V_{1}]$ is $(p-1)$-regular-free subgraph and $H[V_{2}]$ is
$(q-1)$-regular-free subgraph of $H$.

##  4\. Declarations

Conflict of Interest: On behalf of all authors, the corresponding author
states that there is no conflict of interest.

Data Availability Statement:No data were generated or used in the preparation
of this paper.

## References

  * [1] Allan Bickle.  Structural results on maximal k-degenerate graphs.  Discussiones Mathematicae Graph Theory, 32(4):659–676, 2012.
  * [2] Allan Bickle.  Maximal k-degenerate graphs with diameter 2.  Mathematical Combinatorics, 2:68–79, 2021.
  * [3] Allan Bickle and Zhongyuan Che.  Wiener indices of maximal k-degenerate graphs.  Graphs and Combinatorics, 37(2):581–589, 2021.
  * [4] Béla Bollobás and Bennet Manvel.  Optimal vertex partitions.  Bull. London Math. Soc., 11(2):113–116, 1979.
  * [5] Oleg V Borodin and Alexandr V Kostochka.  On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density.  Journal of Combinatorial Theory, Series B, 23(2-3):247–250, 1977\.
  * [6] O.V Borodin and A.V Kostochka.  On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density.  Journal of Combinatorial Theory, Series B, 23(2):247–250, 1977\.
  * [7] Paul A. Catlin.  Brooks’ graph-coloring theorem and the independence number.  J. Combin. Theory Ser. B, 27(1):42–48, 1979.
  * [8] Daniel W Cranston and Landon Rabern.  Graphs with $\chi$=$\delta$ have big cliques.  SIAM Journal on Discrete Mathematics, 29(4):1792–1814, 2015.
  * [9] Andrew D. King.  Hitting all maximum cliques with a stable set using lopsided independent transversals.  Journal of Graph Theory, 67(4):300–305, 2011.
  * [10] Don R Lick and Arthur T White.  k-degenerate graphs.  Canadian Journal of Mathematics, 22(5):1082–1096, 1970.
  * [11] N.N. Mozhan.  Chromatic number of graphs with a density that does not exceed two-thirds of the maximal degree.  Metody Diskretn. Anal, 39:52–65, 1983.
  * [12] Landon Rabern.  On hitting all maximum cliques with an independent set.  Journal of Graph Theory, 66(1):32–37, 2011.
  * [13] Bruce Reed.  A strengthening of brooks’ theorem.  Journal of Combinatorial Theory, Series B, 76(2):136–149, 1999\.
  * [14] Yaser Rowshan and Ali Taherkhani.  A catlin-type theorem for graph partitioning avoiding prescribed subgraphs.  Discrete Mathematics, 345(8):112911, 2022.
  * [15] Yaser Rowshan and Ali Taherkhani.  Partitioning of a graph into induced subgraphs not containing prescribed cliques.  Discrete Applied Mathematics, 344:68–80, 2024.
  * [16] JMS Simoes-Pereira.  Joins of n-degenerate graphs and uniquely (m, n)-partitionable graphs.  Journal of Combinatorial Theory, Series B, 21(1):21–29, 1976.
  * [17] Justus von Postel, Thomas Schweser, and Michael Stiebitz.  Point partition numbers: decomposable and indecomposable critical graphs.  Discrete Mathematics, 345(8):112903, 2022.