# When removing an independent set is optimal for reducing the chromatic
number

Stijn Cambie Mathematics Institute, University of Warwick, UK. E-mail:
<EMAIL_ADDRESS>Supported by the UK Research and Innovation Future
Leaders Fellowship MR/S016325/1. John Haslegrave Mathematical Institute,
University of Oxford, UK. E-mail<EMAIL_ADDRESS>Supported by the UK
Research and Innovation Future Leaders Fellowship MR/S016325/1 and by the
European Research Council under the European Union’s Horizon 2020 research and
innovation programme (grant agreement no. 883810). Ross J. Kang Department of
Mathematics, Radboud University Nijmegen, Netherlands. Email:
<EMAIL_ADDRESS>Supported by a Vidi grant (639.032.614) of the
Netherlands Organisation for Scientific Research (NWO).

(March 2022)

###### Abstract

How large must the chromatic number of a graph be, in terms of the graph’s
maximum degree, to ensure that the most efficient way to reduce the chromatic
number by removing vertices is to remove an independent set? By a reduction to
a powerful, known stability form of Brooks’ theorem, we answer this question
precisely, determining the threshold to within two values (and indeed
sometimes a unique value) for graphs of sufficiently large maximum degree.

##  1 Introduction

Given a graph $G$, what is the minimum number of vertices one must remove in
order to reduce its chromatic number? This natural invariant was introduced by
Akbari et al. [1], who called it the chromatic vertex stability number of $G$,
denoted $\operatorname{vs}_{\chi}(G)$, by analogy with the chromatic edge
stability number defined by Staton [8]. There is a wide range of previous
research on related concepts, such as $\chi$-critical graphs (see e.g. [2]),
reducing the chromatic number via other operations (see e.g. [5]), or reducing
other parameters by vertex deletion (see e.g. [7]).

An obvious way to reduce the chromatic number is to start with an optimal
colouring, and remove all vertices of one colour. This is equivalent to
finding an independent set of vertices whose removal reduces the chromatic
number, and the size of the smallest such set is the independent chromatic
vertex stability number, $\operatorname{ivs}_{\chi}(G)$. Akbari et al. [1]
investigated under what circumstances we can guarantee that this is the most
efficient approach, i.e. that the chromatic vertex stability and independent
chromatic vertex stability numbers are equal. They found that
$\operatorname{vs}_{\chi}(G)=\operatorname{ivs}_{\chi}(G)$ for any graph $G$
with $\chi(G)\geq\Delta(G)$, but that there are examples $G$ for which
$\operatorname{vs}_{\chi}(G)<\operatorname{ivs}_{\chi}(G)$ and
$\chi(G)=\frac{\Delta(G)+1}{2}$. They defined the threshold function
$f(\Delta)$ as the smallest quantity such that, for any graph $G$ of maximum
degree $\Delta$, it must hold that
$\operatorname{vs}_{\chi}(G)=\operatorname{ivs}_{\chi}(G)$ provided that
$\chi(G)\geq f(\Delta)$. They asked the following, and felt the answer should
be yes, i.e. they expected their lower bound on $f$ to be best possible.

######  Question 1 ([1, Problem 3.2]).

Is it true that $f(\Delta)\leq\frac{\Delta}{2}+1$, i.e. if $G$ is a graph with
$\chi(G)\geq\frac{\Delta(G)}{2}+1$, does it then always hold that
$\operatorname{vs}_{\chi}(G)=\operatorname{ivs}_{\chi}(G)$?

We answer Question 1 in the negative. Moreover, we settle the problem of
determining $f(\Delta)$ in a strong sense. In fact, we show that it is the
upper bound of Akbari et al. which is close to best possible, in the sense
that $f(\Delta)$ is always close to $\Delta$. Further, we determine
$f(\Delta)$ almost exactly for every sufficiently large $\Delta$, showing that
it takes one of at most two possible values. Our main results on $f$ are
summarised as follows.

######  Theorem 2.

As above, let $f(\Delta)$ be the smallest quantity such that, for any graph
$G$ of maximum degree $\Delta$, it must hold that
$\operatorname{vs}_{\chi}(G)=\operatorname{ivs}_{\chi}(G)$ provided that
$\chi(G)\geq f(\Delta)$. Then, writing
$k_{\Delta}=\left\lfloor\sqrt{\Delta+\frac{1}{4}}-\frac{3}{2}\right\rfloor$,
the following statements hold.

  1. 1.

$f(\Delta)=\Delta$ if $3\leq\Delta\leq 10$.

  2. 2.

$f(\Delta)\geq\Delta+1-k_{\Delta}$ if $\Delta>10$ and moreover there are
infinitely many values for which $f(\Delta)\geq\Delta+2-k_{\Delta}$.

  3. 3.

$f(\Delta)\leq\Delta+2-k_{\Delta}$ for all $\Delta$ sufficiently large.

A schematic for our main, elementary lower-bound construction is given in
Figure 1.

$K_{\chi-2}$$K_{\chi-2}$$K_{\chi}$ Figure 1: Construction for Proposition 8

The proof of the upper bound of Akbari et al. makes use of Brooks’ theorem,
that for $\Delta\geq 3$ a graph $G$ of maximum degree $\Delta$ satisfying
$\chi(G)=\Delta+1$ must contain a clique of order $\chi(G)$. In proving our
upper bound, we use a deep result of Molloy and Reed [6] which may be regarded
as a stability version of Brooks’ theorem: it says that for large $\Delta$ a
chromatic number sufficiently close to this upper bound must also be caused by
some small subgraph.

A natural approach to this problem, implicit in the lower-bound examples of
Akbari et al., is to consider graphs $G$ where the essential difficulty in
reducing the chromatic number lies in destroying all cliques of order
$\chi(G)$, i.e. $G$ for which $\omega(G)=\chi(G)$, the clique vertex stability
number and chromatic vertex stability number are equal, but the independent
clique vertex stability number is larger. Here we have defined the clique
vertex stability number $\operatorname{vs}_{\omega}(G)$ and independent clique
vertex stability number $\operatorname{ivs}_{\omega}(G)$ analogously, as the
size of the smallest (independent) vertex set whose removal reduces the clique
number of $G$. We give two general constructions based on this approach, both
attaining $\chi(G)\approx\frac{2}{3}\Delta(G)$; by a result of King [5], this
is best possible. While our first construction of this form is simpler, the
second is related to the satisfiability problem and so may be of independent
interest.

We prove our upper bound in Section 2, and give a construction attaining it
(up to a difference of $1$) in Section 3. We then consider the simultaneous
clique and chromatic number version of the problem in Section 4, giving two
essentially optimal constructions. We tie all the ends together for Theorem 2
in Section 5.

##  2 A precise upper bound for the threshold function

Let
$k_{\Delta}=\left\lfloor\sqrt{\Delta+\frac{1}{4}}-\frac{3}{2}\right\rfloor,$
i.e. the maximum integer $k$ for which $(k+1)(k+2)\leq\Delta$. In this
section, we prove the following, which is our main result.

######  Theorem 3.

Let $G$ be a graph with sufficiently large maximum degree $\Delta$ and
chromatic number $\chi(G)=c+1,$ for some $c\geq\Delta+1-k_{\Delta}.$ Then
$\operatorname{vs}_{\chi}(G)=\operatorname{ivs}_{\chi}(G)$.

We now proceed to the proof of Theorem 3. We say that a graph $H$ is
$(c+1)$-critical if $\chi(H)=c+1$ and $\chi(H\setminus v)=c$ for every $v\in
V(H)$. Molloy and Reed [6] proved the following.

######  Theorem 4 ([6]).

Under the hypothesis of Theorem 3, $G$ contains a subgraph $H$ such that

  * •

$\lvert H\rvert\leq\Delta+1$, and

  * •

$H$ is $(c+1)$-critical.

Note that it follows that every $(c+1)$-critical subgraph of $G$ has order at
most $\Delta+1$.

We prove the following proposition.

######  Proposition 5.

Under the hypothesis of Theorem 3, let $\mathcal{C}$ be a connected subgraph
of $G$, which is the union of $(c+1)$-critical subgraphs $H$. Then
$\lvert\mathcal{C}\rvert<\Delta+1+k_{\Delta}$.

###### Proof.

First we prove that the intersection of two subgraphs of the form guaranteed
by Theorem 4 is large.

######  Claim 6.

Let $H_{1}$ and $H_{2}$ be two intersecting $(c+1)$-critical subgraphs of $G$.
Then every vertex in $H_{2}\setminus H_{1}$ has at least $c-k_{\Delta}+1$
neighbours in $H_{1}$.

###### Proof of claim.

A $(c+1)$-critical graph has by definition minimum degree $\delta\geq c.$ A
vertex $v$ in $H_{1}\cap H_{2}$ has at most $k_{\Delta}$ non-neighbours in
$H_{1}$ and at most $k_{\Delta}$ non-neighbours in $H_{2}$. Together with the
at most $\Delta$ neighbours of $v$ in $H_{1}\cup H_{2}$, this implies that
$\lvert H_{1}\cup H_{2}\rvert\leq\Delta+1+2k_{\Delta},$ while $\lvert
H_{1}\rvert,\lvert H_{2}\rvert\geq c+1.$ Now $\lvert H_{1}\cap
H_{2}\rvert=\lvert H_{1}\rvert+\lvert H_{2}\rvert-\lvert H_{1}\cup
H_{2}\rvert\geq\Delta+1-4k_{\Delta}.$ For the remainder of this proof, let
$y=\lvert H_{1}\cap H_{2}\rvert$, $x=\lvert H_{2}\setminus H_{1}\rvert$ and
$k=k_{\Delta}.$ Note that the previous arguments give that $y>x$ provided that
$\Delta>8k_{\Delta}$, which holds if $\Delta$ is sufficiently large. Since for
every vertex $v\in H_{1}\cap H_{2}$ we have $\deg_{H_{1}}(v)\geq c$ and
$\deg_{G}(v)\leq\Delta$, there are at most $\Delta-c\leq k$ neighbours of $v$
in $H_{2}\setminus H_{1}$. On the other hand, every vertex in $H_{2}\setminus
H_{1}$ has at least $c-x$ neighbours in $H_{2}\cap H_{1}$. Double counting of
the edges between $H_{2}\setminus H_{1}$ and $H_{2}\cap H_{1}$ implies that
$ky\geq x(c-x).$ Since $x+y=\lvert H_{2}\rvert\leq\Delta+1\leq c+k$, we have
that $k(c+k-x)\geq x(c-x)$, which is equivalent to $k^{2}\geq(x-k)(c-x).$
Letting $g(x)=(x-k)(c-x)$ and noting that this is a concave parabola with
$g(k+1)=g(c-1)=c-k-1>k^{2}$, we conclude that $x\leq k$ (as $x\geq c$ is
impossible for $\Delta$ sufficiently large). Since $\delta(H_{2})\geq c$, the
statement of the claim follows. ∎

Now assume to the contrary that
$\lvert\mathcal{C}\rvert\geq\Delta+1+k_{\Delta}$. Then we can pick
$k_{\Delta}$ vertices in $\mathcal{C}$ not belonging to a fixed
$(c+1)$-critical graph $H_{1}$, such that each of these $k_{\Delta}$ vertices
belongs to some $(c+1)$-critical graph $H_{i}$ intersecting $H_{1}$ (different
vertices may belong to different $H_{i}$). By Claim 6 and the fact that
$\delta(H_{1})\geq c,$ the average degree of a vertex in $H_{1}$ has to be at
least

$c+\frac{(k_{\Delta}+1)(\Delta-2k_{\Delta}+1)}{\Delta+1}\geq\Delta+1-k_{\Delta}+(k_{\Delta}+1)-\frac{2(k_{\Delta}+1)k_{\Delta}}{\Delta+1}>\Delta,$

which is a contradiction. ∎

We use the last proposition and the following result of Haxell [3] to prove
our main result.

######  Theorem 7 ([3]).

For a positive integer $k$, let $G$ be a graph with vertices partitioned into
$r$ cliques of size $\geq 2k$. If every vertex has at most $k$ neighbours
outside its own clique, then $G$ contains an independent set of size $r$.

###### Proof of Theorem 3.

By Theorem 4, it suffice to consider all $(c+1)$-critical subgraphs $H$ of
$G$, each being of size at most $\Delta+1$. By Proposition 5 we know the union
of these form some connected components of small size, i.e. each having at
most $2(c-k_{\Delta})$ vertices. If there are $r$ such components, we know
that $\operatorname{vs}_{\chi}(G)\geq r.$ Now, for an arbitrary
$(c+1)$-colouring of $G$, every component $\mathcal{C}$ has at least
$2k_{\Delta}$ vertices that are coloured with a colour that appears exactly
once on $\mathcal{C}.$ Every vertex in $\mathcal{C}$ has at least $c$
neighbours in the component and as such at most $\Delta-c\leq k_{\Delta}-1$
neighbours outside of this component. For every $1\leq i\leq r$, we pick a
vertex set $S_{i}$ consisting of $2k_{\Delta}$ vertices in component
$\mathcal{C}_{i}$, each of them coloured by a colour appearing only once on
$\mathcal{C}_{i}$. Let $S=\cup_{i=1}^{r}S_{i}$ and consider the graph $G[S]$.
Then by Theorem 7 (adding edges within each set $S_{i}$ if necessary) we can
find an independent set $I$ of size $r$ in $G[S]$, containing one vertex
$v_{i}$ of every $S_{i}$. Now $\chi(G\setminus I)=c=\chi(G)-1$ since no
$(c+1)$-critical graph of size at most $\Delta+1$ is a subgraph of $G\setminus
I.$ This implies that $\operatorname{ivs}_{\chi}(G)\leq r$ and more precisely
we conclude that $\operatorname{ivs}_{\chi}(G)=\operatorname{vs}_{\chi}(G)=r.$
∎

##  3 A corresponding lower bound construction

######  Proposition 8.

For every integer $\chi\geq 4,$ there exists a graph $G$ with
$\omega(G)=\chi(G)=\chi$ and
$\Delta=\chi+\max\left\\{1,\mathopen{}\left\lceil\frac{\chi}{\mathopen{}\left\lceil\sqrt{\chi}\right\rceil\mathclose{}}\right\rceil\mathclose{}-2\right\\}$
for which $\operatorname{vs}_{\chi}(G)<\operatorname{ivs}_{\chi}(G)$.

###### Proof.

We construct $G$ by first taking the disjoint union of a copy of $K_{\chi}$
and two copies of $K_{\chi-2}\wedge aK_{1}$, where
$a=\mathopen{}\left\lceil\sqrt{\chi}\right\rceil\mathclose{}$ and $\wedge$
denotes the graph join. Then we partition the vertices of $K_{\chi}$ into $a$
non-empty subsets $V_{1},V_{2},\ldots,V_{a}$, each of them containing at most
$\mathopen{}\left\lceil\frac{\chi}{a}\right\rceil\mathclose{}$ vertices. For
each copy of the independent set $aK_{1}$, we connect each vertex with a
different subset $V_{i}$ and all of them are connected with the corresponding
copy of $K_{\chi-2}.$ The construction is illustrated in Figure 1. We now
verify that this construction works for all values of $\chi,$ by checking all
of the promised conditions. The $\omega(G)=\chi$ condition is a trivial one.

Condition $\chi(G)=\chi$: Since $K_{\chi}\subset G,$ we have
$\chi(G)\geq\chi.$ In the other direction, first colour the copy of $K_{\chi}$
with $\chi$ colours. Now pick two colours $c_{1}$ appearing in $V_{1}$ and
$c_{2}$ in $V_{2}$. All vertices in the copies of $aK_{1}$ can be coloured
with either $c_{1}$ or $c_{2}$ (sometimes both are possible). The copies of
$K_{\chi-2}$ can now be coloured with the $\chi-2$ colours different from
$c_{1}$ and $c_{2}.$

Condition $\operatorname{vs}_{\chi}(G)=2$: First we prove that
$\chi(G\setminus v)=\chi$ for every $v\in G$. If $v$ does not belong to the
copy of $K_{\chi}$, then $\chi\leq\chi(G\setminus v)\leq\chi(G)=\chi$. If
$v\in K_{\chi}$, then in neither copy of $K_{\chi-2}\wedge aK_{1}$ is a vertex
removed. If it were possible to colour $G\setminus v$ with $\chi-1$ colours,
the vertices in each copy of $aK_{1}$ would be all coloured with one colour,
being different from the ones used in the corresponding copy of $K_{\chi-2}$.
But the central clique which has become a $K_{\chi-1}$ needs all $\chi-1$
colours as well, so at least one of the copies of $aK_{1}$ is adjacent to a
vertex with the same colour, a contradiction. And so indeed $\chi(G\setminus
v)=\chi$. This implies that $\operatorname{vs}_{\chi}(G)\geq 2.$

For two vertices $u$ and $v$ from the central clique $K_{\chi}$, we have
$\chi(G\setminus\\{u,v\\})=\chi-1.$ For this, note that we can colour the two
copies of $aK_{1}$ with one colour and the three copies of $K_{\chi-2}$ with
the remaining $\chi-2$ other colours. So we conclude that
$\operatorname{vs}_{\chi}(G)=2.$

Condition $\operatorname{ivs}_{\chi}(G)>2$: On the other hand, if we take a
independent set $S$ of size $2$, we have $\chi(G\setminus S)=\chi$. If $S$
does not contain a vertex of the copy of $K_{\chi}$, this is clear. Otherwise,
there is a copy of $aK_{1}\wedge K_{\chi-2}$ from which no vertex is removed.
But then we conclude that $\chi(G\setminus S)>\chi-1$ as we did when verifying
the condition $\operatorname{vs}_{\chi}(G)>1$. This implies that
$\operatorname{ivs}_{\chi}(G)>2.$

Condition on the maximum degree: There are three types of vertices. A vertex
in a copy of $K_{\chi-2}$ has degree $\chi-3+a.$ A vertex in a copy of
$aK_{1}$ has maximum degree at most
$(\chi-2)+\mathopen{}\left\lceil\frac{\chi}{a}\right\rceil\mathclose{}.$ Since
$\mathopen{}\left\lceil\frac{\chi}{a}\right\rceil\mathclose{}\geq a-1$, this
is at least $\chi-3+a.$ A vertex in the copy of $K_{\chi}$ has degree
$(\chi-1)+2=\chi+1.$ This concludes the proof. ∎

######  Remark 9.

Note that one can do the same construction with
$\mathopen{}\left\lceil\frac{\chi}{a}\right\rceil\mathclose{}-1$ copies of
$K_{\chi-2}\wedge aK_{1}$. This has the same maximum degree, and now
$\operatorname{vs}_{\chi}(G)=2$, while
$\operatorname{ivs}_{\chi}(G)=\mathopen{}\left\lceil\frac{\chi}{a}\right\rceil\mathclose{}$.
So even under the condition that $\chi$ and $\Delta$ are close, the difference
between $\operatorname{ivs}_{\chi}$ and $\operatorname{vs}_{\chi}$ can be
unbounded.

##  4 Relations with clique stability

In this section we give two essentially optimal constructions with
$\omega(G)=\chi(G)$ where both the chromatic vertex stability and the clique
vertex stability differ from their independent versions. Note that, while in
general $\operatorname{ivs}_{\omega}(G)$ might not exist, the condition
$\omega(G)=\chi(G)$ ensures that it does, since removing a colour class of an
optimal colouring reduces the chromatic number and so must also reduce the
clique number.

King [5, Theorem 3] proved that for every graph $G$ with
$\omega(G)>\frac{2}{3}(\Delta(G)+1)$, there is an independent set $I$ for
which $\omega(G\setminus I)<\omega(G)$. Although he did not explicitly state
it, his construction clearly shows that there do not exist smaller vertex sets
$S$ for which $\omega(G\setminus S)<\omega(G)$. So stated differently, he
proved the following theorem.

######  Theorem 10 ([5]).

If a graph $G$ satisfies $\omega(G)>\frac{2}{3}(\Delta(G)+1)$, then
$\operatorname{ivs}_{\omega}(G)$ exists and equals
$\operatorname{vs}_{\omega}(G)$.

This theorem is sharp for the clique-blow-up of $C_{5}$, i.e. the graph
$G_{k}$ obtained by substituting every vertex of a $5$-cycle with a clique of
size $k$. In that case $\omega(G_{k})=2k$, $\Delta(G_{k})=3k-1$ and
$\chi(G_{k})=\mathopen{}\left\lceil\frac{5k}{2}\right\rceil\mathclose{}$. For
this graph, $\operatorname{ivs}_{\omega}(G_{k})$ is undefined, while
$\operatorname{vs}_{\omega}(G_{k})=3$. On the other hand,
$\operatorname{vs}_{\chi}(G_{k})=\operatorname{ivs}_{\chi}(G_{k})$ equals $1$
or $2$ depending on the parity of $k$.

We give two constructions for which $\chi(G)=\omega(G)$ and such that
$\operatorname{vs}_{\chi}(G)<\operatorname{ivs}_{\chi}(G)$, provided
$\chi(G)<\frac{2}{3}(\Delta(G)+1)$.

Figure 2: The construction of Proposition 11 for $\Delta=3$ and $\Delta=6$

######  Proposition 11.

For every integer $\Delta\geq 2$, there exists a graph $G$ with
$\omega(G)=\chi(G)=\bigl{\lceil}\frac{2}{3}(\Delta+1)\bigr{\rceil}-1$ such
that
$\operatorname{vs}_{\chi}(G)=\operatorname{vs}_{\omega}(G)<\operatorname{ivs}_{\omega}(G)=\operatorname{ivs}_{\chi}(G)$.

###### Proof.

Let $k=\bigl{\lceil}\frac{2}{3}(\Delta+1)\bigr{\rceil}-1$ and let
$a=2k-\Delta$. Let $H$ be the union of two $K_{k}$’s such that they have $a$
vertices in common, i.e. the intersection of the two $K_{k}$’s is a $K_{a}$.
Now construct $G$ as follows. We take $k$ disjoint copies of $H$ and one
additional copy of $K_{k}$. Connect each vertex of $K_{k}$ to the $a$ vertices
belonging to both $K_{k}$s of a different copy of $H$. The resulting graphs
are presented for $\Delta\in\\{3,6\\}$ in Figure 2, or in a more schematic way
in Figure 3. Observe that $G$ satisfies
$\Delta(G)=\max\\{2k-a,k-1+a\\}=\Delta.$ Since $k-a\geq 1$, it is also not
hard to see that $\chi(G)=\omega(G)=k.$ Furthermore we have
$\operatorname{vs}_{\chi}(G)=k+1,$ since we need to remove at least one vertex
of the central $K_{k}$ and one vertex of each copy of $H$. If we choose the
vertex to be one of the $a$ vertices belonging to both $K_{k}$s in the
construction of $H$, it is also clear that after removing the $k+1$ vertices
we end with a graph with chromatic number equal to $k-1.$ On the other hand
$\operatorname{vs}_{\chi}(G)=k+2,$ since we cannot take an independent set
with precisely one vertex of the $K_{k}$ and every $K_{a}\subset H$. ∎

$H$$H$$H$$H$$H$$K_{k}$$K_{k}$$K_{k}$$K_{a}$$K_{k-a}$ Figure 3: Schematic of
the construction used in Proposition 11

Our second example is based on SAT. Define $p$-LIT $q$-SAT to be the class of
SAT instances such that each clause contains exactly $q$ literals, and each
literal appears at most $p$ times. Note that we permit the $q$ literals in a
clause to contain the same literal more than once, up to the limit of $p$
total occurrences of that literal.

Given a SAT instance $\mathcal{I}$ with $k$ clauses, the independence graph
$G(\mathcal{I})$ consists of one vertex for each literal in each clause, with
two vertices being adjacent if either they are in the same clause or they
correspond to complementary literals. This graph (or its complement) may be
used to prove the NP-hardness of the independent set (or clique) problem,
since $\mathcal{I}$ is satisfiable if and only if $G(\mathcal{I})$ has an
independent set of order $k$; see [4].

We also define the augmented independence graph $\widetilde{G}(\mathcal{I})$,
which is obtained from $G(\mathcal{I})$ by adding two extra vertices for each
clause, adjacent to all vertices from that clause, but not to each other.

######  Proposition 12.

For each $m\geq 2$ there exists an instance $\mathcal{I}$ of $m$-LIT
$(2m-1)$-SAT which is not satisfiable and has $\chi(G(\mathcal{I}))=2m$.

Note that this is tight, in the sense that every instance of $m$-LIT $2m$-SAT
is satisfiable. To see this, draw a bipartite multigraph between pairs of
complementary literals and clauses, with an edge between a pair and a clause
for each time either literal from the pair appears in the clause. Double-
counting edges, each set $S$ of clauses is adjacent to at least $\lvert
S\rvert$ pairs, so Hall’s theorem allows us to select a different pair
adjacent to each clause, and hence to select one literal from each clause no
two of which are complementary, yielding a satisfying assignment. This
argument is due to Tovey [9, Theorem 2.4].

###### Proof.

Let $r=\mathopen{}\left\lceil\log_{2}m\right\rceil\mathclose{}$. We will
inductively construct a sequence $\mathcal{I}_{0},\ldots,\mathcal{I}_{r}$ such
that $\mathcal{I}_{i}$ is an instance of $m$-LIT $(2m-2^{r-i})$-SAT which is
not satisfiable and has $\chi(G(\mathcal{I}_{i}))\leq 2m$. Our construction
will also ensure that $G(\mathcal{I}_{i})$ contains a clique of order $2m$ for
every $i\geq 1$. Thus $\mathcal{I}_{r}$ will satisfy the requirements of the
theorem.

Take $\mathcal{I}_{0}$ to consist of two clauses, one consisting of $2m-2^{r}$
copies of $a$ and the other of $2m-2^{r}$ copies of $\overline{a}$. By
definition of $r$ we have $2^{r-1}<m$, and so the clauses are non-empty and it
is impossible to satisfy both of them. Each literal occurs $2m-2^{r}\leq m$
times, and $G(\mathcal{I}_{0})$ is a clique on $4m-2^{r+1}\leq 2m$ vertices,
so $\mathcal{I}_{0}$ has the required properties.

Now, for each $i=1,\ldots,r$, construct $\mathcal{I}_{i}$ from
$\mathcal{I}_{i-1}$ as follows. For each clause $x$ of $\mathcal{I}_{i-1}$ we
create two clauses $x^{+},x^{-}$ of $\mathcal{I}_{i}$. To do this, choose a
new variable $b_{x}$, and separate the $2m-2^{r-i+1}$ literals appearing in
$x$ (arbitrarily) into two groups of $m-2^{r-i}$. Set $x^{+}$ to consist of
$m$ copies of $b_{x}$ together with the first group, and set $x^{-}$ to
consist of $m$ copies of $\overline{b_{x}}$ together with the second group.
Since each literal from $\mathcal{I}_{i-1}$ appears the same number of times
in $\mathcal{I}_{i}$, and each new literal appears $m$ times, it is indeed an
instance of $m$-LIT $(2m-2^{r-i})$-SAT.

Suppose that a truth assignment satisfies $\mathcal{I}_{i}$. Then for each
clause $x$ of $\mathcal{I}_{i-1}$, it satisfies both $x^{+}$ and $x-$ and
therefore must satisfy $x$. Since $\mathcal{I}_{i-1}$ was not satisfiable,
neither is $\mathcal{I}_{i}$.

Finally, we show that $\chi(G(\mathcal{I}_{i}))\leq 2m$; since the graph
contains a copy of $K_{2m}$ for every new variable $b_{x}$, we must also have
equality. Take a colouring of $G(\mathcal{I}_{i-1})$ with at most $2m$
colours. Note that the subgraph of $G(\mathcal{I}_{i})$ induced by literals
appearing in $\mathcal{I}_{i-1}$ is a subgraph of $G(\mathcal{I}_{i-1})$,
since any two such literals appearing in the same clause of $\mathcal{I}_{i}$
came from the same clause of $\mathcal{I}_{i-1}$. Consequently this is a
proper partial colouring of $G(\mathcal{I}_{i})$. We extend it to the new
literals. For each pair $x^{+},x^{-}$, write $C_{x}^{+}$ (respectively
$C_{x}^{-}$) for the set of colours already used on $x^{+}$ (respectively
$x^{-}$). Note that, since we started from a proper colouring of
$G(\mathcal{I}_{i-1})$, we have $C_{x}^{+}\cap C_{x}^{-}=\varnothing$. Assign
the colours in $C_{x}^{+}$ to $m-2^{r-i}$ of the $\overline{b_{x}}$ literals,
and the colours in $C_{x}^{-}$ to $m-2^{r-i}$ of the $b_{x}$ literals. Since
the two sets were disjoint, this is still a proper partial colouring. Assign
the $2^{r-i+1}$ colours in $[2m]\setminus(C_{x}^{+}\cup C_{x}^{-})$ to the
$2^{r-i+1}$ remaining copies of $b_{x}$ and $\overline{b_{x}}$. Since each of
these only has neighbours in $x^{+}$ or $x^{-}$, this gives a proper colouring
of $G(\mathcal{I}_{i})$. ∎

For example, with $m=4$, the construction might proceed

$\displaystyle\mathcal{I}_{0}$ $\displaystyle=(a\vee a\vee a\vee
a)\wedge(\overline{a}\vee\overline{a}\vee\overline{a}\vee\overline{a}),$
$\displaystyle\mathcal{I}_{1}$ $\displaystyle=(b\vee b\vee b\vee b\vee a\vee
a)\wedge(\overline{b}\vee\overline{b}\vee\overline{b}\vee\overline{b}\vee
a\vee a)$ $\displaystyle\phantom{{}={}}\wedge(c\vee c\vee c\vee
c\vee\overline{a}\vee\overline{a})\wedge(\overline{c}\vee\overline{c}\vee\overline{c}\vee\overline{c}\vee\overline{a}\vee\overline{a}),$
$\displaystyle\mathcal{I}_{2}$ $\displaystyle=(d\vee d\vee d\vee d\vee b\vee
b\vee
a)\wedge(\overline{d}\vee\overline{d}\vee\overline{d}\vee\overline{d}\vee
b\vee b\vee a)$ $\displaystyle\phantom{{}={}}\wedge(e\vee e\vee e\vee
e\vee\overline{b}\vee\overline{b}\vee
a)\wedge(\overline{e}\vee\overline{e}\vee\overline{e}\vee\overline{e}\vee\overline{b}\vee\overline{b}\vee
a)$ $\displaystyle\phantom{{}={}}\wedge(f\vee f\vee f\vee f\vee c\vee
c\vee\overline{a})\wedge(\overline{f}\vee\overline{f}\vee\overline{f}\vee\overline{f}\vee
c\vee c\vee\overline{a})$ $\displaystyle\phantom{{}={}}\wedge(g\vee g\vee
g\vee
g\vee\overline{c}\vee\overline{c}\vee\overline{a})\wedge(\overline{g}\vee\overline{g}\vee\overline{g}\vee\overline{g}\vee\overline{c}\vee\overline{c}\vee\overline{a}).$

Note, however, that the splitting of each clause is arbitrary, and while at
the first step there is only one way to do this, subsequently there are
genuine options producing non-isomorphic constructions.

We next show that we may reduce the chromatic number of $G(\mathcal{I})$ by
removing one vertex from each clause.

######  Lemma 13.

Let $G$ be a $k$-chromatic graph and let $P$ be a partition of $V(G)$ such
that each part induces a clique. Then we can choose a set $S$ consisting of
one vertex from each part such that $G-S$ is $(k-1)$-colourable.

###### Proof.

Colour $G$ with $k$ colours, and choose a highest-coloured vertex from each
part to make up $S$. Since each part has at most one vertex of colour $k$,
every vertex of colour $k$ is in $S$, so at most $k-1$ colours are used on
$G-S$.∎

Finally, we show that the augmented independence graph has the required
properties. An example for $2$-LIT $3$-SAT is shown in Figure 4.

Figure 4: The graph $\tilde{G}(\mathcal{I})$ where $\mathcal{I}$ is the
unsatisfiable $2$-LIT $3$-SAT instance $(b\vee b\vee
a)\wedge(\overline{b}\vee\overline{b}\vee a)\wedge(c\vee
c\vee\overline{a})\wedge(\overline{c}\vee\overline{c}\vee\overline{a})$.
Dotted lines separate clauses, and removing the highlighted vertices reduces
the chromatic number.

######  Proposition 14.

The graph $G=\widetilde{G}(\mathcal{I})$ satisfies $\Delta(G)=3m$ and
$\chi(G)=\omega(G)=2m$ but
$\operatorname{vs}_{\chi}(G)=\operatorname{vs}_{\omega}(G)<\operatorname{ivs}_{\omega}(G)\leq\operatorname{ivs}_{\chi}(G)$.

###### Proof.

Each vertex in $G(\mathcal{I})$ has $2m-2$ neighbours in the same clause and
at most $m$ other neighbours corresponding to the complementary literal, with
some vertices (all except possibly those from $\mathcal{I}_{0}$) having
exactly this many. In $G$, each degree increases by $2$, and the new vertices
have lower degree, so $\Delta(G)=3m$. We have already established that
$\chi(G(\mathcal{I}))=2m$, and we may greedily extend a $2m$-colouring of
$G(\mathcal{I})$ to one of $G$ since each uncoloured vertex has degree $2m-1$.

By Lemma 13, we can remove a set $S$ consisting of one vertex from each clause
of $G(\mathcal{I})$ to reduce its chromatic number. We can extend a
$(2m-1)$-colouring of $G(\mathcal{I})-S$ to one of $G-S$, since each
uncoloured vertex only has $2m-2$ neighbours in $V(G)\setminus S$. Thus
$\operatorname{vs}_{\chi}(G)=\lvert S\rvert$.

Note that each vertex in $V(G)\setminus V(G(\mathcal{I}))$ is in a clique of
order $2m$ in $G$. There are $2\lvert S\rvert$ such cliques, each meeting
exactly one other. Thus the only way to remove $\lvert S\rvert$ vertices from
$G$ and reduce the clique number is to remove one vertex from each of the
$\lvert S\rvert$ intersections, i.e. one vertex from each clause of
$G(\mathcal{I})$. However, since $\mathcal{I}$ is unsatisfiable, there is no
independent set of this form. Thus
$\operatorname{ivs}_{\chi}(G)\geq\operatorname{ivs}_{\omega}(G)>\lvert
S\rvert$. ∎

##  5 Wrapping up

###### Proof of Theorem 2.

For the first part, by [1, Theorem 1] we know $f(\Delta)\leq\Delta$. For
$\Delta\leq 10$, we have constructed graphs with
$\operatorname{vs}_{\chi}(G)<\operatorname{ivs}_{\chi}(G)$ and
$\chi(G)=\Delta(G)-1$ for $\Delta\in\\{3,4\\}$ in Section 4 (Proposition 11)
and for $5\leq\Delta\leq 10$ in Proposition 8. The construction for $\Delta=5$
has been depicted separately in Figure 5.

The second part is due to our construction in Proposition 8. A small
computation verifies that for $\chi=\Delta-k_{\Delta}$ (note that
$k_{\Delta}\geq 1$ when $\Delta>10$), we have
$\chi+\mathopen{}\left\lceil\frac{\chi}{\mathopen{}\left\lceil\sqrt{\chi}\right\rceil\mathclose{}}\right\rceil\mathclose{}-2\leq\Delta.$
The latter is equivalent to showing that

$\Delta-k_{\Delta}\leq(k_{\Delta}+2)\bigl{\lceil}\sqrt{\Delta-
k_{\Delta}}\bigr{\rceil}.$

If $\sqrt{\Delta-k_{\Delta}}\leq k_{\Delta}+2,$ this is clear. By definition
of $k_{\Delta}$ we have $\Delta<(k_{\Delta}+2)(k_{\Delta}+3)$ and so the
statement is again true when $\mathopen{}\left\lceil\sqrt{\Delta-
k_{\Delta}}\right\rceil\mathclose{}\geq k_{\Delta}+3$.

For every $\Delta$ for which $(k+1)(k+2)\leq\Delta\leq k^{2}+4k+1$ for some
positive integer $k\geq 1$, and there are infinitely many such $\Delta$, we
have $(k+1)^{2}<\Delta-k+1\leq(k+1)(k+2).$ This implies that for $\chi=\Delta-
k_{\Delta}+1$ we have
$\chi+\mathopen{}\left\lceil\frac{\chi}{\mathopen{}\left\lceil\sqrt{\chi}\right\rceil\mathclose{}}\right\rceil\mathclose{}-2\leq\Delta$
since
$\chi\leq(k+1)\mathopen{}\left\lceil\sqrt{\chi}\right\rceil\mathclose{}.$

The third part is proven in Theorem 3. ∎

Figure 5: A graph $G$ with
$\Delta(G)=5,\chi(G)=4,\operatorname{ivs}_{\chi}(G)=3$ and
$\operatorname{vs}_{\chi}(G)=2$

### Open access statement.

For the purpose of open access, a CC BY public copyright license is applied to
any Author Accepted Manuscript (AAM) arising from this submission.

## References

  * [1] S. Akbari, A. Beikmohammadi, S. Klavžar, and N. Movarraei.  On the chromatic vertex stability number of graphs.  European J. Combin., 102:Paper No. 103504, 7, 2022.
  * [2] B. Farzad, M. Molloy, and B. Reed.  $(\Delta-k)$-critical graphs.  J. Combin. Theory Ser. B, 93(2):173–185, 2005.
  * [3] P. E. Haxell.  A note on vertex list colouring.  Combin. Probab. Comput., 10(4):345–347, 2001.
  * [4] R. M. Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85–103, 1972.
  * [5] A. D. King.  Hitting all maximum cliques with a stable set using lopsided independent transversals.  J. Graph Theory, 67(4):300–305, 2011.
  * [6] M. Molloy and B. Reed.  Colouring graphs when the number of colours is almost the maximum degree.  J. Combin. Theory Ser. B, 109:134–195, 2014.
  * [7] D. Paulusma, C. Picouleau, and B. Ries.  Reducing the clique and chromatic number via edge contractions and vertex deletions.  In Combinatorial optimization, volume 9849 of Lecture Notes in Comput. Sci., pages 38–49. Springer, [Cham], 2016.
  * [8] W. Staton.  Edge deletions and the chromatic number.  Ars Combin., 10:103–106, 1980.
  * [9] C. A. Tovey.  A simplified NP-complete satisfiability problem.  Discrete Appl. Math., 8(1):85–89, 1984.