# Hadwiger’s Conjecture with Certain Forbidden Induced Subgraphs

Daniel Carter

###### Abstract

We prove that $\\{\overline{K_{3}},H\\}$-free graphs are not counterexamples
to Hadwiger’s Conjecture, where $H$ is any one of 33 graphs on seven, eight,
or nine vertices, or $H=K_{8}$. This improves on past results of Plummer-
Stiebitz-Toft, Kriesell, and Bosse. The proofs are mostly computer-assisted.

##  1 Introduction

All graphs in this paper are finite and simple. Let $h(G)$ be the maximum $t$
such that $K_{t}$ is a minor of $G$, $\chi(G)$ the chromatic number of $G$,
and $\omega(G)$ and $\alpha(G)$ respectively the clique number and
independence number of $G$. Hadwiger’s Conjecture is:

######  Conjecture 1.

For all graphs $G$, $h(G)\geq\chi(G)$.

For a graph $H$, we say $G$ is $H$-free if no induced subgraph of $G$ is
isomorphic to $H$. Likewise for a set of graphs $S$, we say $G$ is $S$-free if
$G$ is $H$-free for all $H$ in $S$. We denote by HC-$S$ the statement that
Hadwiger’s Conjecture holds for all $S$-free graphs.

There is much interest in the specific case of Hadwiger’s Conjecture for
graphs with no stable set of size 3, i.e. $\overline{K_{3}}$-free graphs. Paul
Seymour writes about this case:

> This seems to me to be an excellent place to look for a counterexample. My
> own belief is, if it is true for graphs with stability number two then it is
> probably true in general. [Sey16]

Previously, it was proved:

######  Theorem 1.

HC-$\\{\overline{K_{3}},H\\}$ holds where $H$ is any graph on five vertices or
the graphs $H_{6}$ or $H_{7}$ in Figure 1 [PST03, Kri10], or the wheel graph
on six vertices $W_{5}$, $\overline{K_{1,5}}$, or $K_{7}$ [Bos19].

Figure 1: The graphs $H_{6}$ (left) and $H_{7}$ (right).

We improve these results using three main facts:

######  Lemma 1.

[PST03] Any minimal counterexample to HC-$\\{\overline{K_{3}}\\}$ has no
dominating edges.

Here, a dominating edge is an edge $uv$ such that all vertices are adjacent to
$u$ or $v$ (or both), and by minimal counterexample we mean that no proper
induced subgraph is also a counterexample.

######  Lemma 2.

[CS12] Any $\overline{K_{3}}$-free graph with

$\omega(G)\geq\begin{cases}\lceil\frac{\lvert G\rvert}{4}\rceil&\text{if
$\lvert G\rvert$ is even,}\\\ \lceil\frac{\lvert G\rvert+3}{4}\rceil&\text{if
$\lvert G\rvert$ is odd}\end{cases}$

has $h(G)\geq\chi(G)$.

######  Lemma 3.

$\\{K_{3},H\\}$-free graphs have chromatic number at most $k$, where $(H,k)$
is any of the pairs $(K_{1},0)$, $(K_{2},1)$, $(P_{4},2)$, or $(T_{1},3)$,
$(T_{2},3)$, or $(T_{3},3)$ [Ran04],111In fact, $(T_{1}^{\prime},3)$ is also
such a pair where $T_{1}^{\prime}$ is $T_{1}$ with a second leaf added to the
third vertex in the 5-path [SWY21]. The author was not aware of this stronger
result until after finding the main theorem of this paper. Replacing $T_{1}$
by $T_{1}^{\prime}$ in the relevant algorithm could potentially lead to
slightly better results. where $T_{i}$ are shown in Figure 2.

Figure 2: The trees $T_{1}$, $T_{2}$, and $T_{3}$ (left-to-right) associated
with Lemma 3.

By starting from a graph that is known to be an induced subgraph of any
counterexample to HC-$\\{\overline{K_{3}}\\}$ and iteratively applying these
lemmas, it is sometimes possible to find a new graph that must be an induced
subgraph of any counterexample to HC-$\\{\overline{K_{3}}\\}$. Specifically,
Lemma 1 implies, given a dominating edge $uv$, the existence of a vertex
adjacent to neither $u$ or $v$, which can attach onto the graph in some number
of ways. If there are no dominating edges, we can use the other two lemmas to
get the existence of one or more vertices that attach onto the graph in such a
way as to introduce new dominating edges.

In particular, we prove:

######  Theorem 2.

HC-$\\{\overline{K_{3}},H\\}$ holds where
$H\in\\{H_{1}^{\prime},H_{2}^{\prime},\dots,H_{33}^{\prime}\\}$ is any of the
graphs in Figure 3.

(e)[0.75em]c—c—c—c—c—cc—c—c—c—c—c 1234567 & 1234567 1234567 1234567 1234567
12345678
12345678 12345867 12345678 12345678 12345678 12345678
12345678 12345678 12345678 12345678 12345678 12345678
12345678 12345678 12345678 12345678 12345678 12345678
12345678 12345678 12345678 12345678 12345678 12345678
123456789 123456879 123456798

Figure 3: The complements of the graphs
$H_{1}^{\prime},\dots,H_{33}^{\prime}$, when read from left-to-right, top-to-
bottom. We display the complements because these graphs have many edges, so it
is almost always easier to recognize them from their complements. The graphs
are first ordered by number of vertices, then by common structural elements.
The labelings are used to choose edges in a consistent manner for algorithms.

A small number of these cases are easily proved by hand, but most require
hundreds of steps and are proved with computer assistance. We describe the
relevant algorithms, prove their correctness, and prove some facts about their
behavior and limitations in Section 2. We then provide the data necessary to
verify Theorem 2 in Section 3, and we prove a few of the simple cases by hand
for demonstration. We make some final remarks in Section 4.

###  1.1 Relationship to Past Results

Theorem 2 improves dramatically on Theorem 1. In fact, the only graphs in the
statement of Theorem 1 that are not an induced subgraph of any graph in the
statement of Theorem 2 are $H_{7}$ and $K_{7}$.

By Proposition 1, if HC-$\\{\overline{K_{3}},K_{8}\\}$ holds then Algorithm 4
can prove this fact, though it may take an extremely long time. In fact, since
the Ramsey number $R(3,8)=28$, the algorithm will most likely have to consider
27-vertex graphs at some point. Each such graph accrues a “weight” of
$2^{27}=134217728$ (see Section 4), which is already nearly 6 times the
highest total weight of any of the proof steps in Figure 5 used to prove
Theorem 2, and there are 477142 $\\{\overline{K_{3}},K_{8}\\}$-free graphs
with 27 vertices [BGSP12], so one should not expect to improve $K_{7}$ to
$K_{8}$ by running Algorithm 4 for any reasonable amount of time. Instead, one
should just check these 477142 graphs directly for counterexamples to
HC-$\\{\overline{K_{3}}\\}$, since all graphs with 26 or fewer vertices have
large enough clique number to satisfy the hypothesis of Lemma 2 due to the
exact known values of the Ramsey numbers $R(3,k)$ with $k\leq 7$. Our initial
hope was that Theorem 2 would make this check very easy, but this could not be
further from the truth. In fact, all $\\{\overline{K_{3}},K_{8}\\}$-free
graphs on 27 vertices contain all of the $H_{i}^{\prime}$ (and $H_{7}$), so
Theorem 2 is no help at all. Instead, we perform a check using other means in
Appendix C, and get:

######  Theorem 3.

HC-$\\{\overline{K_{3}},K_{8}\\}$ holds.

and also

######  Corollary 1.

A minimal counterexample to HC-$\\{\overline{K_{3}}\\}$ has either 31 vertices
or at least 33 vertices.

###### Proof.

By the theorem above, a minimal counterexample must have a $K_{8}$. If such a
graph has fewer than 31 vertices or has 32 vertices exactly, Lemma 2 implies
it is not a counterexample to HC-$\\{\overline{K_{3}}\\}$. ∎

Since $R(3,9)=36$, it seems computationally infeasible to improve $K_{8}$ to
$K_{9}$ by brute-force.

The fact that $H_{7}$ was not improved to a larger graph is due primarily to
the combination of the facts that the “$\overline{C_{4}}$-core” of $H_{7}$ is
all of $H_{7}$ (see Section 2.4.2), and $H_{7}$ has no dominating edges. The
only way $H_{7}$ could be improved by the algorithms in this paper is directly
starting from $H_{7}$ itself, but this is a poor starting place given the lack
of dominating edges.

##  2 Algorithms

###  2.1 Basic Algorithm: No Dominating Edges

Suppose all counterexamples to HC-$\\{\overline{K_{3}}\\}$ are known to
contain induced subgraph $H$, i.e. HC-$\\{\overline{K_{3}},H\\}$ holds. If $H$
has a dominating edge $uv$, then by Lemma 1, all minimal counterexamples to
HC-$\\{\overline{K_{3}}\\}$ have an induced $H$ plus a vertex $w$ adjacent to
neither $u$ nor $v$. Since all minimal counterexamples have this property, any
graph containing any minimal counterexample as an induced subgraph will also
have this property, i.e. this holds for all counterexamples, not just minimal
ones. Denote by $H_{uv}$ the set of graphs formed by attaching a new vertex
$w$ to $H$ in all possible ways while making sure $w$ is not adjacent to $u$
or $v$ (there are only finitely many such attachments). We see that
HC-$(\\{\overline{K_{3}}\\}\cup H_{uv})$ holds. In fact, we can remove from
$H_{uv}$ all graphs containing $\overline{K_{3}}$ and the result will still
hold, since of course no $\overline{K_{3}}$-free graph could contain a graph
that itself contains $\overline{K_{3}}$. Let $H_{uv}^{-}$ denote this
“reduced” set of graphs containing no $\overline{K_{3}}$.

Suppose that some $H^{\prime}\in H_{uv}^{-}$ has a dominating edge
$u^{\prime}v^{\prime}$. Applying the same logic as before, we see that
HC-$(\\{\overline{K_{3}}\\}\cup(H_{uv}^{-}\setminus
H^{\prime})\cup(H^{\prime})_{u^{\prime}v^{\prime}}^{-})$ holds. We can repeat
this process for as long as we like, at least until we run into graphs with no
more dominating edges.

If we impose some additional restriction on counterexamples, say that they
satisfy some property $P$, and modify this process to also remove from
$H_{uv}$ all graphs satisfying $P$, in some cases we can completely run out of
graphs, concluding that all counterexamples HC-$\\{\overline{K_{3}}\\}$
satisfy $P$. This is possible when $P$ is monotone, that is, if $H$ satisfies
$P$ and $G$ has induced subgraph $H$ then $G$ also satisfies $P$. Consider
then Algorithm 1.

Input: Monotone property $P$, graph $H$ that is known to be an induced
subgraph of any counterexample to HC-$\\{\overline{K_{3}}\\}$.

Let $A\leftarrow\\{H\\}$;

while  _$A$ is nonempty_ do

Let $H^{\prime}\in A$;

Let $A\leftarrow A\setminus\\{H^{\prime}\\}$;

if  _$H^{\prime}$ has no dominating edges_ then

return _failure_ ;

else

Let $uv$ be a dominating edge of $H^{\prime}$;

for  _$N\in 2^{V(H^{\prime})\setminus\\{u,v\\}}$_ do

Let $G$ be $H^{\prime}$ plus a new vertex $w$ such that the neighbors of $w$
are $N$;

if  _$G$ has no stable set of size 3, $G$ does not satisfy $P$, and $G$ is
$A$-free_ then

Let $A\leftarrow A\cup\\{G\\}$;

return _success_ ;

Algorithm 1 Prove that all counterexamples to HC-$\\{\overline{K_{3}}\\}$
satisfy monotone property $P$.

We now prove the correctness of the algorithm.

######  Lemma 4.

If Algorithm 1 returns success, then all counterexamples to
HC-$\\{\overline{K_{3}}\\}$ satisfy property $P$.

###### Proof.

We claim that, inductively, at the start of each iteration of the main while
loop, $A$ is always set of graphs such that all counterexamples to
HC-$\\{\overline{K_{3}}\\}$ either satisfy $P$ or contains one of the graphs
in $A$ as an induced subgraph. The base case, when $A=\\{H\\}$, is clear.

Suppose $H^{\prime}\in A$ has a dominating edge $uv$. Then if a counterexample
to HC-$\\{\overline{K_{3}}\\}$ contained $H^{\prime}$ as induced subgraph, it
must also have a vertex $w$ that is nonadjacent to both $u$ and $v$. Thus if a
counterexample contained $H^{\prime}$, it must actually contain one of the
graphs $G$ obtained by attaching to $H$ in all possible ways while being
nonadjacent to $u$ and $v$. If $G$ has a stable set of size 3 then it is
obviously not a counterexample to HC-$\\{\overline{K_{3}}\\}$ (and any graph
containing $G$ is also not a counterexample to HC-$\\{\overline{K_{3}}\\}$).
Additionally, if $G$ satisfies $P$, then since $P$ is monotone, any
counterexample containing $G$ will also satisfy $P$. Finally, note that the
set of $A$-free graphs is the same as the set of $(A\cup\\{G\\})$-free graphs
if $G$ contains one of the graphs in $A$ as an induced subgraph. Thus if a
counterexample to HC-$\\{\overline{K_{3}}\\}$ contained $H^{\prime}$ as
induced subgraph, either it satisfies $P$ or it contains as an induced
subgraph one of the graphs contained in $A$ at the end of the inner for loop
(which is the same as $A$ at the beginning of the next iteration of the while
loop). This completes the inductive step.

The condition for the while loop to terminate and the algorithm to return
success is that $A$ is empty at the start of the while loop. If this is the
case, that means that all counterexamples to HC-$\\{\overline{K_{3}}\\}$
satisfy $P$ by the claim just proven. ∎

Of interest in this paper, the property of containing a particular induced
subgraph $H^{\prime}$ is monotone, so in some cases this can be used to prove
that all counterexamples to HC-$\\{\overline{K_{3}}\\}$ have an induced
$H^{\prime}$, i.e. HC-$\\{\overline{K_{3}},H^{\prime}\\}$ holds, so long as
the graphs $H$ and $H^{\prime}$ are chosen carefully and we get lucky. For an
example, see the proof of case $I_{21}$ in Section 3 (and see Figure 4 for a
picture of the complement of this graph). However, it is quite likely that one
will run into a graph with no dominating edges, no stable set of size three,
and with no induced $H^{\prime}$, in which case the algorithm will return
failure. We can often deal with these cases using Lemmas 2 and 3, by a process
described in the next subsection.

###  2.2 Getting Unstuck: Four-Clique Covers

####  2.2.1 Assuming No Vertex Dominates $H$

The restriction that a graph has no stable set of size three means that if two
vertices have a common nonneighbor, they must be adjacent. Thus if $H$ is an
induced subgraph of $G$ and no vertex in $G\setminus H$ is adjacent to all
vertices in $H$, then the vertices of $G\setminus H$ partition into cliques
based on the intersection of their neighborhood with $H$. Additionally, to
avoid stable sets of size 3 and monotone property $P$, many pairs of these
cliques must be complete to each other, i.e. there must be no nonedges between
vertices in those two cliques. In many cases, one can find four cliques
$Q_{1},Q_{2},Q_{3},Q_{4}$ that cover $G$ such that

$\sum_{i=1}^{4}\lvert Q_{i}\cap V(H)\rvert\geq\lvert H\rvert+2,$

so by Pigeonhole Principle, $\omega(G)\geq\lceil\frac{\lvert
G\rvert+2}{4}\rceil$. Note that

$\left\lceil\frac{\lvert
G\rvert+2}{4}\right\rceil\geq\begin{cases}\lceil\frac{\lvert
G\rvert}{4}\rceil&\text{if $\lvert G\rvert$ is even,}\\\ \lceil\frac{\lvert
G\rvert+3}{4}\rceil&\text{if $\lvert G\rvert$ is odd,}\end{cases}$

so by Lemma 2, $G$ is not a counterexample to HC-$\\{\overline{K_{3}}\\}$. If
this is the case, we conclude that all counterexamples with an induced $H$
either satisfy property $P$ or have a vertex adjacent to every vertex in $H$.
The graph obtained by adding to $H$ a vertex adjacent to all vertices in $H$
is known as the coning of $H$, and we denote it in this paper by $H\vee K_{1}$
(for we will generalize this construction in a later subsection). In other
words, all counterexamples with an induced $H$ either satisfy property $P$ or
have an induced $H\vee K_{1}$.222This is the main idea in Bosse’s proof of
HC-$\\{\overline{K_{3}},W_{5}\\}$, with $H=C_{5}$ and $P$ omitted [Bos19],
although that proof used some additional cleverness beyond the algorithm we
describe.

The usefulness of this is that $H\vee K_{1}$ has a dominating vertex, and
therefore dominating edges, for all $H$. Hence it can be used to “unstick”
Algorithm 1 when one encounters a graph with no dominating edges, i.e. when
the algorithm would otherwise return failure. More importantly, this check can
be done completely automatically by Algorithm 2.

Input: Monotone property $P$, graph $H$.

Let $A\leftarrow\varnothing$;

for  _$N\in 2^{V(H)}\setminus\\{V(H)\\}$_ do

Let $G$ be $H$ plus a new vertex $w$ such that the neighbors of $w$ are $N$;

if  _$G$ has no stable set of size 3 and $G$ does not satisfy $P$_ then

Let $A\leftarrow A\cup\\{N\\}$;

Let $B\leftarrow\varnothing$;

for  _$(N_{1},N_{2})\in\binom{A}{2}$_ do

Let $G$ be $H$ plus new vertices $u$ and $v$ such that the neighbors of $u$
are $N_{1}$ and neighbors of $v$ are $N_{2}$;

if  _$G$ has a stable set of size 3 or $G$ satisfies $P$_ then

Let $B\leftarrow B\cup\\{\\{N_{1},N_{2}\\}\\}$;

Let $G$ be $H$ plus vertices $\\{u_{i}\\}_{i=1}^{\lvert A\rvert}$ such that
the neighbors of each $u_{i}$ are $N_{i}$ (where $A=\\{N_{1},\dots,N_{\lvert
A\rvert}\\}$), and $u_{i}$ and $u_{j}$ are adjacent iff $\\{N_{i},N_{j}\\}\in
B$;

if  _there are four cliques $Q_{1},Q_{2},Q_{3},Q_{4}$ covering $G$ such that
$\sum_{i=1}^{4}\lvert Q_{i}\cap V(H)\rvert\geq\lvert H\rvert+2$_ then

return _success_ ;

else

return _failure_ ;

Algorithm 2 Prove that all counterexamples to HC-$\\{\overline{K_{3}}\\}$ that
have an induced $H$ either satisfy monotone property $P$ or have an induced
$H\vee K_{1}$.

We now prove the correctness of this algorithm.

######  Lemma 5.

If Algorithm 2 returns success, then all counterexamples to
HC-$\\{\overline{K_{3}}\\}$ with an induced $H$ either satisfy property $P$ or
have an induced $H\vee K_{1}$.

###### Proof.

Suppose for contradiction Algorithm 2 returned success but there is a
counterexample $G^{\prime}$ to HC-$\\{\overline{K_{3}}\\}$ with an induced $H$
but no induced $H\vee K_{1}$ that does not satisfy property $P$.

Since there is no vertex in $G^{\prime}$ adjacent to all vertices in the
induced $H$, the vertices of $G^{\prime}\setminus H$ partition into at most
$2^{\lvert H\rvert}-1$ cliques based on their neighbors in $H$. Specifically,
if two vertices $u,v$ have identical neighbors in $H$, then by assumption that
$G^{\prime}$ has no indcued $H\vee K_{1}$, $u$ and $v$ have a common
nonneighbor $w\in H$ and must be therefore be adjacent to avoid $\\{u,v,w\\}$
being a stable set of size 3. Some of these potential cliques may be forced to
be empty; for instance if $u,v$ are not adjacent in $H$, all vertices in
$G^{\prime}\setminus H$ must be adjacent to at least one of $u$ and $v$. It is
clear that, after the first for loop, $A$ contains the set of possible
neighborhoods in $H$ of vertices in $G^{\prime}\setminus H$, since the
algorithm filters out all neighborhoods such that if there was a vertex with
that neighborhood, $G^{\prime}$ would either have a stable set of size 3 or
satisfy property $P$ (here using the fact that $P$ is assumed to be monotone).
Note that not all possible neighborhoods are achieved in $G^{\prime}$, but all
vertices in $G^{\prime}\setminus H$ have one of the neighborhoods in $A$. We
identify the cliques in the clique partition of $G^{\prime}\setminus H$ with
the elements of $A$.

Next, suppose $u\in V(G)$ is in clique $N_{1}$ and $v\in V(G)$ is in clique
$N_{2}$, for some $N_{1}\neq N_{2}$. If the graph formed by adding to $H$ the
vertices $u$ and $v$ with neighborhoods $N_{1}$ and $N_{2}$, respectively, has
either a stable set of size 3 or satisfies $P$, then $u$ and $v$ must be
adjacent in $G^{\prime}$. Since this holds for all vertices in $N_{1}$ and
$N_{2}$, in fact $N_{1}$ and $N_{2}$ are complete to each other in
$G^{\prime}$. Then it is clear that, after the second for loop, if
$\\{N_{1},N_{2}\\}\in B$, then $N_{1}$ and $N_{2}$ are complete in
$G^{\prime}$ (though it is possible other pairs of cliques in
$G^{\prime}\setminus H$ could be complete to each other but are not captured
by this for loop).

Since the algorithm returned success, there is a covering of the graph $G$
formed after the second for loop by four cliques $Q_{1},Q_{2},Q_{3},Q_{4}$
such that $\sum_{i=1}^{4}\lvert Q_{i}\cap V(H)\rvert\geq\lvert H\rvert+2$.
Then there is an analogous clique cover of $G^{\prime}$ by four cliques
$Q_{1}^{\prime},Q_{2}^{\prime},Q_{3}^{\prime},Q_{4}^{\prime}$ such that
$\sum_{i=1}^{4}\lvert Q_{i}^{\prime}\cap V(H)\rvert\geq\lvert H\rvert+2$. In
particular,

$Q_{i}^{\prime}=(Q_{i}\cap V(H))\cup\bigcup_{u_{j}\in Q_{i}}(\text{clique in
$G^{\prime}$ corresponding to }N_{j})$

for $i=1,2,3,4$ is such a clique partition. The inequality
$\sum_{i=1}^{4}\lvert Q_{i}^{\prime}\cap V(H)\rvert\geq\lvert H\rvert+2$ is
clear, so we just need to check that the $Q_{i}^{\prime}$ are indeed cliques.
For two $u,v\in Q_{i}^{\prime}$ with $u\neq v$, there are four cases to check:

  * •

If $u,v\in V(H)$, then since $Q_{i}$ is a clique in $G$, $uv$ is an edge of
$H$, so an edge in $G^{\prime}$.

  * •

If $u\in V(H)$ and $v\in(\text{clique corresponding to }N_{j})$ for some $j$
(or symmetrically $v\in V(H)$ and $u\in\text{clique corresponding to }N_{j}$),
then since $Q_{i}$ is a clique in $G$, $uu_{j}$ is an edge of $G$, which means
$u\in N_{j}$ and $uv$ is an edge in $G^{\prime}$ by definition of $N_{j}$.

  * •

If $u,v\in(\text{clique corresponding to }N_{j})$ for some $j$, then obviously
$uv$ is an edge in $G^{\prime}$.

  * •

If $u\in(\text{clique corresponding to }N_{j})$ and $v\in(\text{clique
corresponding to }N_{k})$ for some $j\neq k$, then since $Q_{i}$ is a clique
in $G$, $u_{j}u_{k}$ is an edge of $G$, so $\\{N_{j},N_{k}\\}\in B$ and the
cliques corresponding to $N_{j}$ and $N_{k}$ are complete to each other in
$G^{\prime}$, i.e. $uv$ is an edge in $G^{\prime}$.

This implies by Pigeonhole Principle that
$\omega(G^{\prime})\geq\lceil\frac{\lvert G^{\prime}\rvert+2}{4}\rceil$, but
by Lemma 2 this contradicts that $G^{\prime}$ is a counterexample to
HC-$\\{\overline{K_{3}}\\}$. ∎

####  2.2.2 Weaker or Stronger Assumptions

Sometimes we can get different results than Algorithm 2 with different
assumptions than there being no vertex adjacent to all vertices in an induced
$H$. For instance, if we allow $G$ to have vertices complete to the induced
$H$, but assume that they form a clique, then all vertices in $G$ still
partition into cliques based on the intersection of their neighborhood with
$H$, only now this neighborhood is allowed to be all of $H$. This assumption
implies that $c(G,H)$ is $\overline{K_{2}}$-free, where $c(G,H)$ is the
subgraph of $G\setminus H$ consisting of vertices complete to $H$.

We can make an even weaker assumption on $G$ if we enforce only that $c(G,H)$
has clique cover number equal to at most some constant $k$. This is equivalent
to the assumption that $\overline{c(G,H)}$ is $k$-colorable, since a cover of
$c(G,H)$ by $k$ cliques is a cover of $\overline{c(G,H)}$ by $k$ independent
sets, i.e. color classes. By Lemma 3, $c(G,H)$ having clique cover number at
most $k$ is implied by $c(G,H)$ being $F_{k}$-free, where
$F_{0}=\overline{K_{1}}\cong K_{1}$, $F_{1}=\overline{K_{2}}$,
$F_{2}=\overline{P_{4}}\cong P_{4}$, and $F_{3}=\overline{T_{1}}$.333One could
also take $F_{3}=\overline{T_{2}}$ or $\overline{T_{3}}$. This leads to slight
variations in the algorithm and could potentially lead to different results.
We have not investigated these alternatives. Denote by $G\vee H$ (read “$G$
join $H$”) the graph formed by adding to $G\cup H$ all edges between $G$ and
$H$. In other words, $G\vee H=\overline{\overline{G}\sqcup\overline{H}}$, with
$\sqcup$ the disjoint union of graphs. Then consider Algorithm 3.

Input: Monotone property $P$, graph $H$, integer $k\in\\{0,1,2,3\\}$.

Let $A\leftarrow\varnothing$;

for  _$N\in 2^{V(H)}\setminus\\{V(H)\\}$_ do

Let $G$ be $H$ plus a new vertex $w$ such that the neighbors of $w$ are $N$;

if  _$G$ has no stable set of size 3 and $G$ does not satisfy $P$_ then

Let $A\leftarrow A\cup\\{N\\}$;

Let $B\leftarrow\varnothing$;

for  _$(N_{1},N_{2})\in\binom{A}{2}$_ do

Let $G$ be $H$ plus new vertices $u$ and $v$ such that the neighbors of $u$
are $N_{1}$ and neighbors of $v$ are $N_{2}$;

if  _$G$ has a stable set of size 3 or $G$ satisfies $P$_ then

Let $B\leftarrow B\cup\\{\\{N_{1},N_{2}\\}\\}$;

Let $C\leftarrow\varnothing$;

for  _$N\in A$_ do

Let $G$ be $H$ plus new vertices $u$ and $w$ such that the neighbors of $u$
are $N$ and neighbors of $w$ are $V(H)$;

if  _$G$ has a stable set of size 3 or $G$ satisfies $P$_ then

Let $C\leftarrow C\cup\\{\\{N\\}\\}$;

Let $G$ be $H$ plus vertices $\\{u_{i}\\}_{i=1}^{\lvert
A\rvert}\cup\\{w_{i}\\}_{i=1}^{k}$ such that the neighbors of each $u_{i}$ are
$N_{i}$ (where $A=\\{N_{1},\dots,N_{\lvert A\rvert}\\}$), $u_{i}$ and $u_{j}$
are adjacent iff $\\{N_{i},N_{j}\\}\in B$, the neighbors of each $w_{i}$ are
$V(H)$, none of the $w_{i}$ and $w_{j}$ are adjacent, and $w_{i}$ and $u_{j}$
are adjacent iff $N_{j}\in C$;

if  _there are four cliques $Q_{1},Q_{2},Q_{3},Q_{4}$ covering $G$ such that
$\sum_{i=1}^{4}\lvert Q_{i}\cap V(H)\rvert\geq\lvert H\rvert+2$_ then

return _success_ ;

else

return _failure_ ;

Algorithm 3 Prove that all counterexamples to HC-$\\{\overline{K_{3}}\\}$ that
have an induced $H$ either satisfy monotone property $P$ or have an induced
$H\vee F_{k}$, for chosen $k$.

The correctness of this algorithm follows from essentially the same logic as
Algorithm 2, so we skip some details of the proof.

######  Lemma 6.

If Algorithm 3 returns success, then all counterexamples to
HC-$\\{\overline{K_{3}}\\}$ with an induced $H$ either satisfy property $P$ or
have an induced $H\vee F_{k}$.

###### Proof.

The crux of the argument, as in the previous proof, is that if the $G$
constructed by Algorithm 3 has a cover by cliques
$\\{Q_{1},Q_{2},Q_{3},Q_{4}\\}$ with $\sum_{i=1}^{4}\lvert Q_{i}\cap
V(H)\rvert\geq\lvert H\rvert+2$, then any potential counterexample
$G^{\prime}$ also has a cover by cliques
$\\{Q_{1}^{\prime},Q_{2}^{\prime},Q_{3}^{\prime},Q_{4}^{\prime}\\}$ with
$\sum_{i=1}^{4}\lvert Q_{i}^{\prime}\cap V(H)\rvert\geq\lvert H\rvert+2$, and
therefore has clique number at least $\frac{\lvert G^{\prime}\rvert+2}{4}$.
Now $c(G^{\prime},H)$ is assumed to have clique cover number at most $k$, so
it is covered by $k$ cliques $R_{1},\dots,R_{k}$. The cliques of $G^{\prime}$
are given by

$Q_{i}^{\prime}=(Q_{i}\cap V(H))\cup\bigcup_{u_{j}\in Q_{i}}(\text{clique in
$G^{\prime}$ corresponding to }N_{j})\cup\bigcup_{w_{j}\in Q_{i}}R_{j}.$

We must check that these are cliques. For $u,v\in Q_{i}^{\prime}$ with $u\neq
v$, the new cases not in the previous proof are:

  * •

If $u\in V(H)$ and $v\in R_{j}$ for some $j$, then obviously $uv$ is an edge
of $G$.

  * •

If $u\in\text{clique corresponding to }N_{j}$ and $v\in R_{\ell}$ for some
$j,\ell$, then $N_{j}\in C$, so if $uv$ was a nonedge of $G^{\prime}$,
$G^{\prime}$ would either have a stable set of size 3 or would satisfy $P$.

  * •

If $u,v\in R_{j}$ for some $j$, then $uv$ is an edge of $G$ by assumption that
$R_{j}$ was a clique.

It is not possible for $u\in R_{j}$ and $v\in R_{\ell}$ for some $j\neq\ell$
to both be in the same $Q_{i}^{\prime}$ since the $w_{i}\in V(G)$ form a
stable set.

Therefore if $c(G^{\prime},H)$ has clique cover number at most $k$,
$G^{\prime}$ is not a counterexample to HC-$\\{\overline{K_{3}}\\}$. So by
Lemma 3, $c(G^{\prime},H)$ has an induced $F_{k}$, so $G^{\prime}$ has an
induced $H\vee F_{k}$. ∎

Recall that the purpose of Algorithms 2 and 3 is to “unstick” Algorithm 1 by
introducing new dominating edges. However, the results of these algorithms in
general are much stronger than what is necessary to unstick Algorithm 1.
Define $\operatorname{dom}(H)$ to be the set of graphs formed from $H$ by
adding one vertex, such that the resulting graph has at least one dominating
edge. Then weakest possible variation of this idea would be Algorithm 2 but
replacing $P$ with the logical-or of $P$ and the negation of being
$\operatorname{dom}(H)$-free. Since $H\vee K_{1}\in\operatorname{dom}(H)$ for
any $H$, if this modified algorithm returns success then all counterexamples
to HC-$\\{\overline{K_{3}}\\}$ that have an induced $H$ either satisfy $P$ or
have one of the members of $\operatorname{dom}(H)$ as an induced subgraph.

###  2.3 Combined Algorithm

The algorithms in Section 2.2 can be easily incorporated into Algorithm 1 to
form Algorithm 4.

Input: Monotone property $P$, graph $H$ that is known to be an induced
subgraph of any counterexample to HC-$\\{\overline{K_{3}}\\}$, boolean $E$.

if  _$H$ satisfies $P$_ then

return _success_ ;

Let $A\leftarrow\\{H\\}$;

while  _$A$ is nonempty_ do

Let $H^{\prime}\in A$;

Let $A\leftarrow A\setminus\\{H^{\prime}\\}$;

if  _$H^{\prime}$ has a dominating edge_ then

Let $uv$ be a dominating edge of $H^{\prime}$;

for  _$N\in 2^{V(H^{\prime})\setminus\\{u,v\\}}$_ do

Let $G$ be $H^{\prime}$ plus a new vertex $w$ such that the neighbors of $w$
are $N$;

if  _$G$ has no stable set of size 3, $G$ does not satisfy $P$, and $G$ is
$A$-free_ then

Let $A\leftarrow A\cup\\{G\\}$;

else

for  _$k\in\\{3,2,1,0\\}$ (in the order written)_ do

if  _Algorithm 3 returns success when given input $(P,H^{\prime},k)$_ then

if  _$H^{\prime}\vee F_{k}$ has no stable set of size 3, $H^{\prime}\vee
F_{k}$ does not satisfy $P$, and $H^{\prime}\vee F_{k}$ is $A$-free_ then

Let $A\leftarrow A\cup\\{H^{\prime}\vee F_{k}\\}$;

Break out of the inner for loop;

if  _the previous for loop was not broken out of_ then

if  _Algorithm 2 returns success when given input
$(P\vee\neg\text{``$\operatorname{dom}(H^{\prime})$-free''},H^{\prime})$_ then

for  _$H^{\prime\prime}\in\operatorname{dom}(H^{\prime})$_ do

if  _$H^{\prime\prime}$ has no stable set of size 3, $H^{\prime\prime}$ does
not satisfy $P$, and $H^{\prime\prime}$ is $A$-free_ then

Let $A\leftarrow A\cup\\{H^{\prime\prime}\\}$;

else

if  _$H^{\prime}$ is not a counterexample to HC-$\\{\overline{K_{3}}\\}$_ then

for  _$N\in 2^{V(H^{\prime})}$_ do

Let $G$ be $H^{\prime}$ plus a new vertex $w$ such that the neighbors of $w$
are $N$;

if  _$G$ has no stable set of size 3, $G$ does not satisfy $P$, and $G$ is
$A$-free_ then

Let $A\leftarrow A\cup\\{G\\}$;

else

return _failure_ ;

return _success_ ;

Algorithm 4 Prove that all counterexamples to HC-$\\{\overline{K_{3}}\\}$
satisfy monotone property $P$.

The correctness of this algorithm follows almost immediately from Lemmas 4, 5,
and 6. There are just two parts of the algorithm that have not been explained.
First, we add a check at the beginning of the algorithm, and if $H$ already
satisfies $P$ then we immediately return success. Second, the final check
performed is that if $H^{\prime}$ is not a counterexample to
HC-$\\{\overline{K_{3}}\\}$, then any counterexample to
HC-$\\{\overline{K_{3}}\\}$ that has an induced $H^{\prime}$ must actually
have an $H^{\prime}$ plus one vertex, though the edges incident to this vertex
have no restriction other than that the resulting graph is
$\overline{K_{3}}$-free and does not satisfy $P$.

In actuality, Algorithm 4 never had to perform the final check on any input we
have given it in the process of discovering Theorem 2. Thus we never actually
implemented the final check. However, it is not difficult to construct
examples of $H^{\prime}$ such that the second-to-last check (Algorithm 2 run
with modified $P$) returns failure; for instance this will happen if it is
given the complement of any triangle-free 5-chromatic graph. The smallest such
graphs have 22 vertices [JR95]. Thus if one was to extend our computations
substantially farther, one might want to add this additional check.

This algorithm’s behavior is dependent on the method of choosing $H^{\prime}$
and a dominating edge $uv$ in cases that $A$ has more than one element or
$H^{\prime}$ has more than one dominating edge. There are theoretical reasons
to prefer some methods over others, which we describe in the next subsection.
We describe some miscellaneous implementation details in Appendix A.

###  2.4 Behavior of the Algorithm

####  2.4.1 Ordering

As we mentioned, the intermediate steps of the algorithm depend on the method
employed to choose $H^{\prime}$ from $A$ and one dominating edge from
$H^{\prime}$ in the event there are multiple possibilities. In this paper we
are only interested in deterministic ways of doing this. Let $\mathcal{A}$ be
one particular implementation of Algorithm 4, i.e. one possible method of
choosing graphs and edges. More precisely, $\mathcal{A}$ consists of a
collection of (computable, deterministic) functions: one that chooses an
element $H^{\prime}\in A$, one that chooses a dominating edge $uv\in
H^{\prime}$ if $H^{\prime}$ has at least one such edge, and some that
determine the order to consider graphs in the innermost for loops. These
functions are allowed to take as input auxiliary memory that may be modified
at any point in the algorithm. For instance, $\mathcal{A}$ may remember some
vertex labeling in graphs, remember the order that graphs were added or
removed from $A$, remember the number of iterations of various loops, etc. and
use this information to determine which graph or dominating edge to consider
next.

Let us write $H\vdash_{\mathcal{A}}P$ (read “$H$ proves $P$ (under
implementation $\mathcal{A}$)”) if the $\mathcal{A}$ implementation of
Algorithm 4 returns success given input $(H,P)$, and write
$H\vdash_{\mathcal{A}}G$ if $H\vdash_{\mathcal{A}}P$ when $P$ is the property
of having an induced $G$. There are several highly desirable traits that we
would like to be true:

  1. 1.

For any $H$, $H\vdash_{\mathcal{A}}H$, i.e. $\vdash_{\mathcal{A}}$ is
reflexive.

  2. 2.

If $H\vdash_{\mathcal{A}}G$ and $G\vdash_{\mathcal{A}}P$ then
$H\vdash_{\mathcal{A}}P$, i.e. $\vdash_{\mathcal{A}}$ is transitive.

  3. 3.

If $H$ is an induced subgraph of $H^{\prime}$ and $H\vdash_{\mathcal{A}}P$
then $H^{\prime}\vdash_{\mathcal{A}}P$, i.e. $\vdash_{\mathcal{A}}$ is
monotone decreasing on the left with respect to taking induced subgraphs.

  4. 4.

If $G$ is an induced subgraph of $G^{\prime}$ and
$H\vdash_{\mathcal{A}}G^{\prime}$ then $H\vdash_{\mathcal{A}}G$, i.e.
$\vdash_{\mathcal{A}}$ is monotone increasing on the right with respect to
taking induced subgraphs. More generally, if $P$ is a stricter property than
$P^{\prime}$ in the sense that any graph satisfying $P^{\prime}$ also
satisfies $P$, and $H\vdash_{\mathcal{A}}P^{\prime}$, then
$H\vdash_{\mathcal{A}}P$.

This would make $\vdash_{\mathcal{A}}$, when restricted to the case that $P$
is the property of having an induced $G$, a quasi-order on graphs that
respects the induced subgraph partial order. The first property is obviously
true for any $\mathcal{A}$ due to the check at the very beginning of Algorithm
4. Additionally, there is a simple condition on $\mathcal{A}$ needed to make
property (4) hold:

######  Theorem 4.

If $\mathcal{A}$ has the following properties, then if $P$ is a stricter
property than $P^{\prime}$ and $H\vdash_{\mathcal{A}}P^{\prime}$, then
$H\vdash_{\mathcal{A}}P$:

  * •

$\mathcal{A}$ always chooses the most recently added $H^{\prime}$ from $A$,

  * •

the order that graphs are added to $A$ depends only on the $H^{\prime}$ chosen
in that iteration of the while loop (not on $A$ or $P$ or anything else),
and444Note that this is only a condition on the order that the graphs are
considered. Obviously whether or not they are added to $A$ depends on $P$ and
$A$, but they must be considered in the same order no matter what.

  * •

the dominating edge chosen when there are multiple possibilities depends on
$H^{\prime}$ only as well.

###### Proof.

Suppose $H\vdash_{\mathcal{A}}P^{\prime}$, and consider the set of graphs
$S^{\prime}$ that are ever a member of $A$ when the algorithm is run with
input $(H,P^{\prime})$. Since $H\vdash_{\mathcal{A}}P^{\prime}$, this set is
finite. Construct a directed acyclic graph $D^{\prime}$ with vertex set
$S^{\prime}$ and an edge from $v$ and $u$ if $v$ is an induced subgraph of
$u$. Then the order that graphs are removed from $A$ corresponds to a depth-
first search on $D^{\prime}$, by virtue of always choosing the latest-added
graph to $A$ in each iteration.

If $P$ is a stricter property than $P^{\prime}$, then the corresponding set
$S$ when the algorithm is run with input $(H,P)$ is a subset of $S^{\prime}$,
and the corresponding directed acyclic graph $D$ is a subgraph of
$D^{\prime}$. To see this, consider the sequences
$\mathcal{S}_{1}=\\{A_{1},\dots,A_{k}\\}$ and
$\mathcal{S}_{2}=\\{A_{1}^{\prime},\dots,A_{\ell}^{\prime}\\}$ consisting of
the set $A$ snapshotted at the beginning of each iteration of the main while
loop when the algorithm is run with input $(H,P)$ and $(H,P^{\prime})$,
respectively.

We will show there is a injection $f:\mathcal{S}_{1}\to\mathcal{S}_{2}$ such
that $A\subset f(A)$ for all $A\in\mathcal{S}_{1}$. More strongly, the
relative order that graphs were added to $A$ is the same as the relative order
they were added in $f(A)$. This injection is constructed as follows:
$f(A_{i})$ is the $A_{j}^{\prime}$ such that if $H_{i}\in A_{i}$ is the graph
chosen by $\mathcal{A}$ at the beginning of the while loop at that iteration
(i.e. the most recently added graph to $A$ at that point in time), then
$H_{i}$ is also the graph chosen in $A_{j}^{\prime}$. To see that this is
well-defined and has the desired properties, we use induction. This is
obviously true for $A_{1}=\\{H\\}=A_{1}^{\prime}=f(A_{1})$.

To see that $f(A_{i+1})$ exists and has the desired properties given
$f(A_{i})$ does, either $H_{i+1}$ is in $A_{i}$ or not. If it is, then
$H_{i+1}$ is also in $A_{j}^{\prime}=f(A_{i})$. On some iteration $j_{2}>j$ of
the algorithm run on $(H,P^{\prime})$, $H_{i+1}$ must be the most recently
added graph in $A_{j_{2}}$. This is the chosen value of $f(A_{i+1})$. The fact
that the rest of $A_{i+1}$ is in $f(A_{i+1})$ with the same relative order
follows from inductive hypothesis because the rest of $A_{i+1}$ is older than
$H_{i+1}^{\prime}$ and also appears in $A_{i}$ in the same relative order.
Thus the rest of $A_{i+1}$ appears in $f(A_{i})$ and, since the rest is older
than $H_{i+1}^{\prime}$, is untouched until after iteration $j_{2}$.

If $H_{i+1}$ is not in $A_{i}$, then it was added to $A$ in iteration $i$
under input $(H,P)$, possibly alongside some other graphs. Therefore if
$A_{j}^{\prime}=f(A_{i})$, $H_{i+1}$ was added to $A$ in iteration $j$ under
input $(H,P^{\prime})$, along with the same other graphs as in input $(H,P)$
in the same order, plus possibly some additional graphs interspersed with
these (since $P$ is stricter than $P^{\prime}$). Thus at some iteration
$j_{2}>j$, $H_{i+1}$ will be the most recently added graph under input
$(H,P^{\prime})$, and the rest of the logic follows similarly to the case in
the previous paragraph. This completes the inductive step.

Thus we can conclude $S\subseteq S^{\prime}$ and, more weakly,
$H\vdash_{\mathcal{A}}P$. ∎

Unfortunately, we are unable to find a version of Algorithm 4 that makes all
of the remaining properties true. However, restricted to only the constituent
parts of Algorithm 4 (namely Algorithms 1 and 3), we can come up with results
close to the above properties. We write $H\vdash_{e}P$ if either $H$ satisfies
$P$ or Algorithm 1 returns success given input $(H,P)$ and the implementation
described in the following two paragraphs. Similarly we write $H\vdash_{c}P$
if either $H$ satisfies $P$ or Algorithm 2 returns success given input
$(H,P)$. Note that the output of Algorithm 2 does not depend on implementation
details.

There is a method of choosing dominating edges and elements of $A$ that makes
$\vdash_{e}$ have these properties. Namely, we first label the vertices of $H$
with integers 1 through $\lvert V(H)\rvert$. Whenever a vertex is added to a
graph, it gets the smallest integer label not yet used in that graph. For
$H^{\prime}\vee F_{k}$, the labels of the vertices in the $F_{k}$ part are the
next $\lvert V(F_{k})\rvert$ integers, and relative ordering of vertices in
the $F_{k}$ part is always the same (though this is not strictly necessary).
Edges $uv$ are identified with the tuple $(\max(u,v),\min(u,v))$, where
vertices are identified by their label. The chosen dominating edge is the
minimum edge under the lexicographical ordering with this identification. In
essence, the dominating edge chosen is the one whose younger endpoint is as
old as possible, breaking ties by looking at the other endpoint.

Next, whenever multiple graphs are to be added to $A$, notice that they are
all just $H^{\prime}$ plus one vertex, possibly with some restrictions on the
neighbors of the new vertex. We add these to $A$ in the order such that if
$N_{1}$ and $N_{2}$ are two different sets of the labels of the neighbors of
the newly-added vertex, the graph corresponding to $N_{1}$ is added before
$N_{2}$ iff, after sorting $N_{1}$ and $N_{2}$ and writing them as tuples,
$N_{1}$ comes lexicographically after $N_{2}$. If $N_{1}$ is a prefix of
$N_{2}$, it comes after $N_{2}$; otherwise the one that comes second is the
one with the smallest element in the symmetric difference of $N_{1}$ and
$N_{2}$.

######  Theorem 5.

Under the method of choosing dominating edges and graphs described in the
previous paragraphs:

  1. 1.

If $H\vdash_{e}G$ and $G\vdash_{e}P$ then $H\vdash_{e}P$.

  2. 2.

If $H$ is an induced subgraph of $H^{\prime}$ and $H\vdash_{e}P$ then
$H^{\prime}\vdash_{e}P$.

  3. 3.

If $H\vdash_{e}P$ then $H\vdash_{\mathcal{A}}P$, where the method for choosing
graphs and dominating edges in $\mathcal{A}$ is also as in the previous
paragraphs.

###### Proof.

First, (3) is obvious since Algorithm 4 performs exactly the same computations
as Algorithm 1 given that implementation $\mathcal{A}$ and the fact that
$H\vdash_{e}P$.

For a particular graph $H$, consider the set $S(H)$ of minimal graphs
$H^{\prime}$ containing $H$ so that no dominating edge of $H$ is a dominating
edge of $H^{\prime}$. If $H\vdash_{e}P$, then for each $H^{\prime}\in S(H)$,
either $H^{\prime}$ satisfies $P$ or $H^{\prime}$ has a dominating edge,
because if $H^{\prime}$ did not have a dominating edge and did not satisfy
$P$, then Algorithm 1 would construct it from $H$ and then return failure. In
particular, because the order for choosing dominating edges considers all
dominating edges of $H$ before any edges introduced by adding vertices to $H$,
all members $H^{\prime}$ of $S(H)$ will be constructed by the algorithm unless
a proper induced subgraph of $H^{\prime}$ satisfies $P$. Let $S_{P}(H)$ be the
subset of $S(H)$ that does not satisfy property $P$.

If $H\vdash_{e}P$, then for each $H^{\prime}\in S_{P}(H)$, for each
$H^{\prime\prime}\in S(H^{\prime})$, either $H^{\prime\prime}$ satisfies $P$
or $H^{\prime\prime}$ has a dominating edge. We continue in this manner, but
because $H\vdash_{e}P$, the algorithm terminates at some point, and there must
be a $k$ such that $S_{P}^{k}(H)$ is empty, where $S_{P}^{0}(H)=\\{H\\}$
(unless $H$ already satisfies $P$, in which case $S_{P}^{0}(H)=\varnothing$)
and

$S_{P}^{i}(H)=\bigcup_{H^{\prime}\in S_{P}^{i-1}(H)}S_{P}(H^{\prime})$

for $i\geq 1$.

Now suppose $H$ is an induced subgraph of $I$ and $H\vdash_{e}P$. Then for any
graph $I^{\prime}\in S(I)$, there is a graph $H^{\prime}\in S(H)$ so that
$H^{\prime}$ is an induced subgraph of $H^{\prime}$. This is because in
$I^{\prime}$ none of the dominating edges of $I$ are dominating, which means
none of the dominating edges of the $H$ contained in the $I$ are dominating in
$I^{\prime}$, so $I^{\prime}$ must contain one of the graphs in $S(H)$.
Similarly, for any $I^{\prime}\in S_{P}(I)$, there is an $H^{\prime}\in
S_{P}(H)$ such that $H^{\prime}$ is an induced subgraph of $I^{\prime}$.
Inductively one can then see that for any $i$ and $I^{\prime}\in
S_{P}^{i}(I)$, there is an $H^{\prime}\in S_{P}^{i}(H)$ such that $H^{\prime}$
is an induced subgraph of $I^{\prime}$. Setting $i=k$, since $S_{P}^{k}(H)$ is
empty, $S_{P}^{k}(I)$ must also be empty, which means $I\vdash_{e}P$. This is
(2).

For (1), let $k_{G}$ be the minimum $k$ so that $S_{P}^{k}(G)=\varnothing$ and
$k_{H}$ the minimum $k$ so that $S_{G}^{k}(H)=\varnothing$, where the
subscript $G$ means to consider the property of having an induced $G$. Any
graph $I\in S_{P}^{k_{H}}(H)$ has an induced $G$ and therefore (by the
reasoning in the previous paragraph), $S_{P}^{k_{G}}(I)=\varnothing$. But it
is to prove by induction on $b$ that

$S_{P}^{a+b}(H)=\bigcup_{I\in S_{P}^{a}(H)}S_{P}^{b}(I),$

which proves (1) by setting $a=k_{H}$ and $b=k_{G}$.

∎

Similarly, for Algorithm 2:

######  Theorem 6.

If $H$ is an induced subgraph of $H^{\prime}$, $H\vee K_{1}$ satisfies $P$,
and $H\vdash_{c}P$ then $H^{\prime}\vdash_{c}P$.

###### Proof.

Note if $H^{\prime}$ has $H\vee K_{1}$ as an induced subgraph,
$H^{\prime}\vdash_{c}P$ is immediate. If not, then consider first the case
that $H^{\prime}$ is $H$ plus one vertex $v$, and consider the sets $A$ and
$B$ constructed for the algorithm given input $(H,P)$ and corresponding sets
$A^{\prime}$ and $B^{\prime}$ constructed given input $(H^{\prime},P)$. Then
since $H\vee K_{1}$ satisfies $P$, we find every member of $A^{\prime}$ is
either $N_{i}$ or $N_{i}^{\prime}=N_{i}\cup\\{v\\}$ for some $N_{i}\in A$.
Also, if the neighbors of $v$ are $N$, then $N\neq V(H)$, and $N$ is not in
$A^{\prime}$ (only possibly $N\cup\\{v\\}$) due to the restriction that there
are no stable sets of size 3.

Now the following are members of $B^{\prime}$, assuming the relevant sets are
members of $A^{\prime}$:

  * •

$\\{N_{i},N_{i}^{\prime}\\}$, since there is some $v\in H$ with $v\not\in
N_{i}$ and $v\not\in N_{i}^{\prime}$.

  * •

$\\{N_{i},N_{j}\\}$, $\\{N_{i},N_{j}^{\prime}\\}$, and
$\\{N_{i}^{\prime},N_{j}^{\prime}\\}$ if $\\{N_{i},N_{j}\\}\in B$, since if
$H$ plus two vertices with neighbor sets $N_{i}$ and $N_{j}$ has a stable set
of size 3 or satisfies $P$, $H^{\prime}$ plus two vertices with neighbor sets
($N_{i}$ or $N_{i}^{\prime}$) and ($N_{j}$ or $N_{j}^{\prime}$) also has a
stable set of size 3 or satisfies $P$, which can be seen just by deleting $v$
from the graph after adding the two new vertices.

Thus if $Q_{1},Q_{2},Q_{3},Q_{4}$ are four cliques covering
$G=H\cup\\{u_{i}\\}$ with $\sum_{i=1}^{4}\lvert Q_{i}\cap V(H)\rvert\geq\lvert
H\rvert+2$, then there are
$Q_{1}^{\prime},Q_{2}^{\prime},Q_{3}^{\prime},Q_{4}^{\prime}$ are four cliques
covering $G^{\prime}=H^{\prime}\cup\\{u_{i}\\}\cup\\{u_{i}^{\prime}\\}$ with
$\sum_{i=1}^{4}\lvert Q_{i}^{\prime}\cap V(H^{\prime})\rvert\geq\lvert
H^{\prime}\rvert+2$. Let the neighbors of $v$ in $H$ be $N$, which we can take
without loss of generality to be in $Q_{1}$. Then set

$Q_{i}^{\prime}=\\{u_{i}\mid u_{i}\in Q_{i}\\}\cup\\{u_{i}^{\prime}\mid
u_{i}\in Q_{i}\\}\cup\begin{cases}\\{v,u^{\prime}\\}&\text{if $i=1$}\\\
\varnothing&\text{otherwise}\end{cases}$

and $u_{i}^{\prime}$ is the vertex in $G^{\prime}$ corresponding to set
$N_{i}^{\prime}\in A^{\prime}$ and $u^{\prime}$ the vertex corresponding to
$N\cup\\{v\\}$ where $N$ is the neighbor set of $v$ (unless
$N\cup\\{v\\}\not\in A^{\prime}$, in which case just drop $u^{\prime}$ from
$Q_{1}^{\prime}$). The fact these are cliques follows from $Q_{i}$ being
cliques and each of the pairs of sets noted above being in $B^{\prime}$, and

$\displaystyle\sum_{i=1}^{4}\lvert Q_{i}^{\prime}\cap V(H^{\prime})\rvert$
$\displaystyle\geq 1+\sum_{i=1}^{4}\lvert Q_{i}^{\prime}\cap V(H)\rvert$
($Q_{1}$ contains $v$) $\displaystyle\geq 1+\sum_{i=1}^{4}\lvert Q_{i}\cap
V(H)\rvert$ $\displaystyle\geq\lvert V(H)\rvert+3$ $\displaystyle=\lvert
V(H^{\prime})\rvert+2.$

The full theorem statement then follows easily by induction on $\lvert
V(H^{\prime})\rvert$. ∎

Unfortunately, it does not seem like one can generalize the above theorem to
be valid for Algorithm 3 run with the third input $k>0$. For instance, one can
verify that the algorithm returns success on the input $(F_{1},F_{1}\vee
F_{2},2)$, but failure on $(F_{2},F_{2}\vee F_{1},1)$. Therefore if one wanted
to prove HC-$\\{\overline{K_{3}},F_{1}\vee F_{2}\\}$ using Algorithm 3, you
would succeed if you started from $F_{1}$ but not $F_{2}$, despite $F_{2}$
containing $F_{1}$. There are additional complications if one wanted to
combine Theorems 5 and 6 to say something about the behavior of Algorithm 4,
but this specific failure means that there is probably no implementation or
simple modification to Algorithm 4 that makes all the desired properties hold
unless one severely weakened the algorithm by removing the calls to Algorithm
3 with $k>0$ and the additional checks if Algorithm 3 fails.

####  2.4.2 Limitations

We begin this section with a simple observation:

######  Proposition 1.

If HC-$\\{\overline{K_{3}},K_{n}\\}$ holds for some $n$, the
$H\vdash_{\mathcal{A}}K_{n}$ for all $H$ and $\mathcal{A}$.

###### Proof.

By Ramsey’s Theorem there are only finitely many
$\\{\overline{K_{3}},K_{n}\\}$-free graphs, so Algorithm 4 must terminate. If
HC-$\\{\overline{K_{3}},K_{n}\\}$ holds then Algorithm 4 will not return
failure, so it must return success. ∎

For some $H$ and $G$, we can actually prove the reverse: there is no
$\mathcal{A}$ for which $H\vdash_{\mathcal{A}}G$. Given a graph $I$, define
the $I$-core of a graph $H$ to be the subgraph of $H$ induced by all vertices
that are in an induced $G$ in $H$. Then:

######  Theorem 7.

If $H\vdash_{\mathcal{A}}G$ for some $\mathcal{A}$, then the $I$-core of $G$
is an induced subgraph of the $I$-core of $H$, where $I$ is either:

  1. 1.

$\overline{C_{4}}$,

  2. 2.

any graph with minimum codegree at least 3, i.e. the complement of a graph
with minimum degree at least 3.

###### Proof.

We prove the contrapositive: if the $I$-core of $G$ is not an induced subgraph
of the $I$-core of $H$, then not $H\vdash_{\mathcal{A}}G$ for any
$\mathcal{A}$. In particular, we will prove inductively that at each iteration
of the while loop, $A$ contains at least one graph whose $I$-core does not
contain the $I$-core of $G$. The base case (in either possibility for $I$) is
just the hypothesis of the contrapositive. Also, in either possibility for
$I$, if the $I$-core of the chosen $H^{\prime}\in A$ contains the $I$-core of
$G$, then by inductive hypothesis there is another $H^{\prime\prime}\in A$
whose $I$-core does not contain the $I$-core of $G$, and this
$H^{\prime\prime}$ will still be present in $A$ in the next iteration (unless
the algorithm returned failure). So we may assume the chosen $H^{\prime}\in A$
has an $I$-core that does not contain the $I$-core of $G$.

  1. 1.

If $H^{\prime}$ has a dominating edge, say $\mathcal{A}$ chooses edge $uv$,
then one possible neighbor set of the newly added vertex $w$ is
$V(H^{\prime})\setminus\\{u,v\\}$. Let $H^{\prime\prime}$ be the graph formed
by adding $w$ to $H^{\prime}$. In this case, $w$ cannot possibly be in an
induced $\overline{C_{4}}$ in $H^{\prime\prime}$. If it was, say
$\\{a,b,c,w\\}$ induces $\overline{C_{4}}$ with $a$ adjacent to $b$ and $c$
adjacent to $w$. Since $w$ is not adjacent to $a$ or $b$, we must have
$\\{a,b\\}=\\{u,v\\}$, but then $uv$ was not dominating since $c$ is also
nonadjacent to both $a$ and $b$. Thus the $\overline{C_{4}}$-core of
$H^{\prime\prime}$ is the same as $H^{\prime}$. Therefore $G$ is not an
induced subgraph of $H^{\prime}$. Also $H^{\prime\prime}$ is
$\overline{K_{3}}$-free if $H^{\prime}$ is, since the only nonneighbors of $w$
are $u$ and $v$, which are adjacent. Therefore either $H^{\prime\prime}$ is
added to $A$ or else there is another $H^{\prime\prime\prime}\in A$ that is an
induced subgraph of $H^{\prime\prime}$. In either case, there is a graph whose
$\overline{C_{4}}$-core does not contain the $\overline{C_{4}}$-core of $G$.

If $H^{\prime}$ has no dominating edge, then if any of the calls to Algorithm
3 succeed, one can verify the new graph to be added to $A$ has the same
$\overline{C_{4}}$-core as $H^{\prime}$, so the inductive step follows in this
case as well by similar logic to above.

If none of the calls to Algorithm 3 succeed, but the call to Algorithm 2
succeeds, then one of the graphs to be added to $A$ is $H\vee K_{1}$. By
similar logic to above, the inductive step holds here.

Finally, if even the call to Algorithm 2 fails, but the final check that
$H^{\prime}$ is not a counterexample to HC-$\\{\overline{K_{3}}\\}$ succeeds,
then one of the graphs to be added to $A$ is $H\vee K_{1}$. By the same logic,
the inductive step holds.

If all checks fail then the algorithm returns failure and it is not the case
that $H\vdash_{\mathcal{A}}G$.

  2. 2.

If $H^{\prime}$ has a dominating edge, say $\mathcal{A}$ chooses edge $uv$,
then one possible neighbor set of the newly added vertex $w$ is
$V(H^{\prime})\setminus\\{u,v\\}$. Noting that $w$ has codegree 2 in
$H^{\prime\prime}$, we see that the $I$-core of $H^{\prime\prime}$ is the same
as the $I$-core of $H^{\prime}$. Then the inductive step follows from the same
logic as in case (1).

If $H^{\prime}$ has no dominating edge, then if any of the calls to Algorithm
3 succeed, one can verify the new graph to be added to $A$ has the same
$\overline{C_{4}}$-core as $H^{\prime}$, so the inductive step follows in this
case as well by similar logic to above. Some care must be taken in the $k=3$
case, since $F_{3}$ has a vertex $w$ of codegree 3. However, none of the
nonneighbors of this vertex have codegree 3 or greater, so it is not part of
any induced subgraph of $H^{\prime}\vee F_{3}$ that has minimum codegree 3
(either an induced subgraph of $H^{\prime}\vee F_{3}$ contains a nonneighbor
of $w$ with codegree less than 3 or $H^{\prime}\vee F_{3}$ does not contain
all nonneighbors of $w$ and $w$ has codegree less than 3 in the induced
subgraph).

The last two cases, if the call to Algorithm 2 succeeds or if it fails, are
identical to case (1).

∎

This means that it is impossible for the techniques in this paper to improve
Theorem 1 to all graphs on six vertices, since the graph $\overline{K_{3,3}}$
(among others) is equal to its $\overline{C_{4}}$-core. It also helps explain
the general patterns in the graphs $H_{i}^{\prime}$, such as the relative lack
of induced $\overline{C_{4}}$’s (compared to induced $\overline{C_{5}}$’s,
say) and abundance of low-codegree vertices (which appear as leaves and
isolated vertices in the drawings of the complements in Figure 3).

##  3 Results

The graphs used in intermediate steps in proving Theorem 2 and in the example
proofs are shown in Figure 4.

###  3.1 Some Simple Cases

First we present a proof of HC-$\\{\overline{K_{3}},I_{21}\\}$ that uses only
Algorithm 1, i.e. only using the fact that minimal counterexamples to
HC-$\\{\overline{K_{3}}\\}$ have no dominating edges. This will involve
several steps starting from the graph $W_{5}$.

(e)[0.75em]c—c—c—c—c—cc—c—c—c—c 123456 & 123456 123456 123456 1234567 1234567
1234567 1234567 1234567 1234567 1234567 1234567
1234567 1234567 1234567 1234567 1234567 1234567
12345678 12345678 12345678 12345678 12345678 12345678
12345687 12345687

Figure 4: The complements of the graphs $I_{1},\dots,I_{26}$ when read left-
to-right, top-to-bottom. These graphs are used in the proof of Theorem 2. As
in Figure 3, the labelings are used to choose edges consistently in
algorithms.

######  Lemma 7.

HC-$\\{\overline{K_{3}},I_{3}\\}$ holds.

###### Proof.

By Theorem 1, any minimal counterexample $G$ to HC-$\\{\overline{K_{3}}\\}$
has an induced $W_{5}$, say induced by vertices 1 through 6 with 1-2-3-4-5-1 a
5-cycle and 6 adjacent to the other five vertices. For edge $(1,6)$ to not be
dominating, there must be a vertex 7 in $G$ adjacent to neither 1 nor 6. Then
7 is adjacent to 3 and 4 (nonneighbors of 1), and at least one of 2 and 5
since $G$ has no stable set of size 3. WLOG, 7 is adjacent to 2 and either
(case 1) adjacent or (case 2) nonadjacent to 5.

(Case 1) For edge $(2,6)$ to not be dominating, $G$ must have a vertex 8
adjacent to neither 2 nor 6. Vertex 8 must be adjacent to 4, 5, and 7. If it
is adjacent to 1, then $\\{1,4,2,8,6,7\\}$ induces $I_{3}$. If 8 is not
adjacent to 1, then delete vertex 7 and witness that the resulting graph is
isomorphic to the graph to be considered in case 2, so we reduce to that case.

(Case 2) For edge $(2,6)$ to not be dominating, $G$ must have a vertex 8
adjacent to neither 2 nor 6. Vertex 8 must be adjacent to 4, 5, and 7. If it
is adjacent to 1, then $\\{1,4,2,8,6,7\\}$ induces $I_{3}$. If not, then it is
adjacent to 3. For edge $(3,6)$ to not be dominating, $G$ must have a vertex 9
adjacent to neither 3 nor 6. Vertex 9 must be adjacent to 1, 5, 7, and 8. If 9
is adjacent to 2 then $\\{2,5,3,9,6,8\\}$ induces $I_{3}$. If it is not, then
it is adjacent to 4 and $\\{2,4,1,7,6,9\\}$ induces $I_{3}$.

Therefore any minimal counterexample (and therefore every counterexample) to
HC-$\\{\overline{K_{3}}\\}$ has an induced $I_{3}$. ∎

######  Lemma 8.

HC-$\\{\overline{K_{3}},I_{14}\\}$ holds.

###### Proof.

By the previous lemma, any minimal counterexample $G$
HC-$\\{\overline{K_{3}}\\}$ has an induced $I_{3}$, say induced by vertices 1
through 6 with 1-2-3-4-5-6-1 a 6-cycle in the complement graph. For edge
$(1,4)$ to not be dominating, $G$ must have a vertex 7 adjacent to neither 1
nor 4. But then since $G$ has no stable set of size 3, 7 must be adjacent to
all four other vertices, and $\\{1,2,3,4,5,6,7\\}$ induces $I_{14}$. ∎

######  Lemma 9.

HC-$\\{\overline{K_{3}},I_{21}\\}$ holds.

###### Proof.

Starting from the endpoint of the proof of the previous lemma, in order for
$(2,5)$ to not be dominating, there must be a vertex 8 adjacent to neither 2
nor 5. Then 8 must be adjacent to all other vertices except possibly 7. If it
is adjacent to 7 then $\\{1,2,3,4,5,6,7,8\\}$ induces $I_{21}$. If not, then
for $(3,6)$ to not be dominating, there must be a vertex 9 adjacent to neither
3 nor 6; this vertex is adjacent to 1, 2, 3, 4, 5, 6, and at least one of 7
and 8. If 7 then $\\{1,2,3,4,5,6,7,9\\}$ induces $I_{21}$; if 8 then
$\\{1,2,3,4,5,6,8,9\\}$ induces $I_{21}$ instead. ∎

This is probably the best result that can be obtained starting from Theorem 1
using Algorithm 1 alone without involving a tremendous amount of casework.

The graph $H_{7}$ in Figure 1 has no dominating edges, but we can using
Algorithm 3 to introduce new vertices and dominating edges into this graph,
and then use Algorithm 1 afterwards. Here is an example, proving eventually
HC-$\\{\overline{K_{3}},I_{12}\\}$.

######  Lemma 10.

HC-$\\{\overline{K_{3}},I_{2}\\}$ holds.

###### Proof.

By Theorem 1, any minimal counterexample $G$ to HC-$\\{\overline{K_{3}}\\}$
has an induced $H_{7}$, say induced by vertices 1 through 7 with 1-2-3-4-5-1 a
5-cycle, 6 adjacent to $\\{1,2,3,7\\}$, and 7 adjacent to $\\{2,3,4,6\\}$.
Suppose for contradiction $G$ had no $I_{2}$.

Then the vertices $v$ of $G\setminus H_{7}$ have $N(v)\cap\\{1,\dots,7\\}$
equal to one of the following sets:

(c)[0.25em]lllccccccccc $N_{0}=\\{3,4,5,7\\}$, & $N_{1}=\\{3,4,5,6,7\\}$,
$N_{2}=\\{2,3,4,6,7\\}$,

$N_{3}=\\{2,3,4,5,7\\}$, $N_{4}=\\{2,3,4,5,6,7\\}$, $N_{5}=\\{1,4,5,7\\}$,

$N_{6}=\\{1,4,5,6,7\\}$, $N_{7}=\\{1,4,5,6\\}$, $N_{8}=\\{1,4,5\\}$,

$N_{9}=\\{1,3,4,5,7\\}$, $N_{10}=\\{1,3,4,5,6,7\\}$, $N_{11}=\\{1,3,4,5,6\\}$,

$N_{12}=\\{1,3,4,5\\}$, $N_{13}=\\{1,2,5,6,7\\}$, $N_{14}=\\{1,2,5,6\\}$,

$N_{15}=\\{1,2,4,5,7\\}$, $N_{16}=\\{1,2,4,5,6,7\\}$,
$N_{17}=\\{1,2,4,5,6\\}$,

$N_{18}=\\{1,2,4,5\\}$, $N_{19}=\\{1,2,3,6,7\\}$, $N_{20}=\\{1,2,3,5,6,7\\}$,

$N_{21}=\\{1,2,3,5,6\\}$, $N_{22}=\\{1,2,3,4,6,7\\}$,
$N_{23}=\\{1,2,3,4,5,7\\}$,

$N_{24}=\\{1,2,3,4,5,6,7\\}$, $N_{25}=\\{1,2,3,4,5,6\\}$,
$N_{26}=\\{1,2,3,4,5\\}$.

(This is easily verified by brute-force; any other neighbor set leads either
to a stable set of size 3 or an $I_{2}$.)

The set of vertices $S_{i}$ for which $N(v)\cap\\{1,\dots,7\\}=N_{i}$ forms a
clique in $G$ for all $i$ except possibly $i=24$ since $G$ has no stable set
of size 3 and such vertices share a nonneighbor except in the case $i=24$.
Suppose, for the moment, that $G$ had no induced $H_{7}\vee\overline{K_{2}}$.
Then $S_{24}$ is also a clique in $G$.

For each pair $(i,j)$ with marked with an X in Table 1, $S_{i}$ and $S_{j}$
must be complete to each other in $G$, since if they weren’t, $G$ would either
have a stable set of size 3 or an $I_{2}$ (again, this can be verified by
brute force by adding two vertices to $G$ with the appropriate neighbors and
making those vertices nonadjacent, then witnessing that the resulting graph
has a $\overline{K_{3}}$ or $I_{2}$).

(c)[0.25em]c—ccccccccccccccccccccccccccc—cccccccccccccccccccccccccc & 0 1 2 3
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
1 X
2 X X
3 X X X
4 X X X X
5 X X X
6 X X X X
7 X X X X X
8 X X X X X X
9 X X X X X X X
10 X X X X X X X X
11 X X X X X X X X X
12 X X X X X X X X X X
13 X X X X X X X X X
14 X X X X X X X
15 X X X X X X X X X X X X
16 X X X X X X X X X X X X X
17 X X X X X X X X X X X X X X
18 X X X X X X X X X X X X X X X
19 X X X
20 X X X X X X X X X X X X X X
21 X X X X X X X X X X X X X X X
22 X X X X X X X X X X X X X
23 X X X X X X X X X X X X X X X X X X
24 X X X X X X X X X X X X X X X X X X X
25 X X X X X X X X X X X X X X X X X X X X
26 X X X X X X X X X X X X X X X X X X X X X

Table 1: Pairs of sets $S_{i}$ and $S_{j}$ that must be complete to each
other. Each such pair with $i>j$ is marked with an X in row $i$, column $j$.

Then the sets given by

  * •

$Q_{1}=\\{4,5\\}\cup S_{0}\cup S_{1}\cup S_{5}\cup S_{6}\cup S_{7}\cup
S_{8}\cup S_{9}\cup S_{10}\cup S_{11}\cup S_{12},$

  * •

$Q_{2}=\\{2,3\\}\cup S_{3}\cup S_{4}\cup S_{20}\cup S_{21}\cup S_{23}\cup
S_{24}\cup S_{25}\cup S_{26},$

  * •

$Q_{3}=\\{2,3,6,7\\}\cup S_{2}\cup S_{19}\cup S_{22},$ and

  * •

$Q_{4}=\\{1,2\\}\cup S_{13}\cup S_{14}\cup S_{15}\cup S_{16}\cup S_{17}\cup
S_{18}$

are a clique cover of $G$, and $\lvert Q_{1}\rvert+\lvert Q_{2}\rvert+\lvert
Q_{3}\rvert+\lvert Q_{4}\rvert\geq\lvert V(G)\rvert+2$, so
$\omega(G)\geq\frac{\lvert V(G)\rvert+2}{4}$, so by Lemma 2, $G$ is not a
counterexample to HC-$\\{\overline{K_{3}}\\}$. This means our supposition that
$G$ was $(H_{7}\vee\overline{K_{2}})$-free was incorrect, so $G$ has a vertex
8 and 9 both adjacent to $\\{1,\dots,7\\}$ but not adjacent to each other.

Then for $(1,8)$ to not be a dominating edge, $G$ must have a vertex 10
adjacent to neither 1 nor 8. Vertex 10 must be adjacent to 3 and 4. If 10 is
adjacent to 2 or 5 then $\\{9,8,10,1,4,2\\}$ or $\\{9,8,10,1,3,5\\}$ induces
$I_{2}$, respectively. But 10 cannot be nonadjacent to both 2 and 5, so we
have a contradiction and $G$ does have an $I_{2}$. ∎

The proof above essentially used Algorithm 3 with $k=1$, finishing by
eliminating a dominating edge. As can be seen, this clique cover technique is
computationally intensive and rather impractical to verify by hand, even for
this relatively small example.

######  Lemma 11.

HC-$\\{\overline{K_{3}},I_{12}\\}$ holds.

###### Proof.

From the previous lemma, any minimal counterexample $G$ of
HC-$\\{\overline{K_{3}}\\}$ has an induced $I_{2}$, say by vertices 1 through
6 with 1-2-3-4-5-6 a 6-path in the complement graph. For $(2,5)$ to not be
dominating, $G$ must have a vertex 7 adjacent to neither 2 nor 5, but this
vertex must be adjacent to 1, 3, 4, and 6, so $\\{2,7,5,4,3,1,6\\}$ induces
$I_{12}$. ∎

###  3.2 Data for Computer Verification

As we discussed in Section 2.4, in Algorithm 1 and Algorithm 4, one needs to
choose a dominating edge whenever a graph has multiple. We describe our method
for this in more detail in Section 2.4 and Appendix A. The vertex labeling of
the initial graph $H$ is given by the labelings in Figures 3 and 4. Whenever a
vertex is added to a graph, it gets the smallest positive integer label not
yet used in that graph. The chosen dominating edge is the one that minimizes
the larger label of its endpoints.

We then present the necessary steps to verify Theorem 2 as a directed forest.
Each edge $G\to H$ means to run Algorithm 4 starting from graph $G$ to prove
HC-$\\{\overline{K_{3}},H\\}$, i.e. it is the assertion
$G\vdash_{\mathcal{A}}H$ for our implementation $\mathcal{A}$ of Algorithm 4.

There are four starting points used: $W_{5}$, $\overline{K_{2,3}}$, $K_{7}$,
and $H_{7}$. All four are known to be induced subgraphs of any counterexample
to HC-$\\{\overline{K_{3}}\\}$ due to Theorem 1. The labeling to use for
$W_{5}$ is to label the vertices in the 5-cycle as 1-2-3-4-5 and the hub as 6.
The labeling to use for $\overline{K_{2,3}}$ is that the part with three
vertices gets labels 1, 3, and 5 and the part with two vertices gets labels 2
and 4. All labelings of $K_{7}$ are equivalent due to symmetry. The labeling
to use for $H_{7}$ is to label a 5-cycle 1-2-3-4-5 and vertex 6 is adjacent to
1, 2, 3, 7 and vertex 7 is adjacent to 2, 3, 4, 7.

The directed forest is shown in Figure 5. There are many other possible
connections between the graphs in the diagram; the arrows we display seek to
minimize the time it takes for a computer to verify each step. We describe
this in more detail in Section 4, as well as explain briefly how this directed
forest was found starting from Theorem 1.

$\overline{K_{2,3}}$$I_{4}$$K_{7}$$H_{2}^{\prime}$$W_{5}$$I_{3}$$H_{7}$$I_{15}$$H_{3}^{\prime}$$I_{2}$$I_{12}$$I_{18}$$I_{14}$$H_{1}^{\prime}$$H_{5}^{\prime}$$I_{25}$$I_{26}$$I_{21}$$I_{1}$$I_{13}$$I_{5}$$H_{33}^{\prime}$$H_{24}^{\prime}$$I_{6}$$I_{8}$$I_{11}$$H_{16}^{\prime}$$I_{19}$$H_{21}^{\prime}$$H_{13}^{\prime}$$I_{7}$$H_{20}^{\prime}$$I_{22}$$I_{16}$$I_{23}$$H_{26}^{\prime}$$I_{20}$$H_{12}^{\prime}$$H_{18}^{\prime}$$H_{32}^{\prime}$$H_{31}^{\prime}$$H_{29}^{\prime}$$I_{24}$$H_{4}^{\prime}$$H_{25}^{\prime}$$H_{14}^{\prime}$$H_{27}^{\prime}$$I_{10}$$H_{7}^{\prime}$$H_{17}^{\prime}$$I_{17}$$H_{15}^{\prime}$$H_{8}^{\prime}$$H_{30}^{\prime}$$H_{10}^{\prime}$$H_{9}^{\prime}$$H_{23}^{\prime}$$H_{28}^{\prime}$$H_{11}^{\prime}$$I_{9}$$H_{6}^{\prime}$$H_{19}^{\prime}$$H_{22}^{\prime}$
Figure 5: The directed forest for verifying Theorem 2.

##  4 Final Remarks

Call the weight (relative to an implementation $\mathcal{A}$ of Algorithm 4)
of input $(H,G)$ the sum over the graphs $H^{\prime}$ added to $A$ at any
point in the algorithm (including $H$) of $2^{\lvert V(H^{\prime})\rvert}$,
assuming $H\vdash_{\mathcal{A}}G$ so that this weight is finite. This measure
is designed to give a very rough estimate of the amount of time it takes for
Algorithm 4 to prove HC-$\\{\overline{K_{3}},G\\}$ starting from $H$. This is
because there are several parts of the algorithm that scale exponentially (or
at least super-polynomially) in the size of the graph $H^{\prime}$ considered
at some point:

  * •

When one constructs graphs by adding a vertex to $H^{\prime}$ while either
avoiding or introducing a dominating edge, there may be exponentially many
such graphs.

  * •

In several places we must solve the subgraph isomorphism problem, which is NP-
complete in general. Even though this is only polynomial-time for fixed $G$,
recall that in some places we check if graphs are $A$-free with $A$ containing
possibly arbitrarily large graphs, so we are still potentially subject to the
full NP-completeness of this problem.

  * •

Running Algorithm 3 requires possibly constructing an auxiliary graph with
exponentially many vertices. Worse, we then try to find a clique cover of this
graph with four cliques, which is equivalent to 4-coloring the complement
graph and is thus NP-complete in general. The total running time of Algorithm
3 is therefore actually potentially doubly-exponential in the number of
vertices of the input.

Weight the directed edges of Figure 5 according to this metric. The proof data
expressed in Figure 5 is optimized to minimize the largest weight in any
individual edge from a graph $H_{i}^{\prime}$ to one of the roots using our
specific implementation of Algorithm 4. In fact, the way these proofs were
found was by running in parallel all inputs $(H,G)$ with $H$ a maximal graph
for which HC-$\\{\overline{K_{3}},H\\}$ is known and $G$ a minimal graph that
is not an induced subgraph of any graph $H^{\prime}$ for which
HC-$\\{\overline{K_{3}},H^{\prime}\\}$ is known, where by “parallel” we mean
at each point in time to step forward whichever instance currently has the
lowest running total weight. In this way, when an instance returns success, we
can be sure it is the most efficient possible improvement.

This was performed starting from the graphs in Theorem 1 until no new
improvements were found with a weight less than $2.3\cdot 10^{7}$. There are
69 minimal graphs that are not a subgraph of any $H_{i}^{\prime}$ or $K_{7}$
or $H_{7}$, though several of these (such as $\overline{K_{3,3}}$) could not
possibly be proved by the methods in this paper due to Theorem 7. We expect if
one continues to run this process, one will continue to find new graphs for
which HC-$\\{\overline{K_{3}},H\\}$ holds for a long time, though the
improvements become less frequent over time.

The weights for each edge in Figure 5 are given in Appendix B.

There are several routes that could improve the results obtained in this
paper. First, an mentioned in a footnote in the introduction, there is a
recent improvement to Lemma 3 [SWY21], so one can replace the tree $T_{1}$
with the larger $T_{1}^{\prime}$ obtained by adding a second leaf attached to
the third vertex of the 5-path of $T_{1}$, and replace $F_{3}$ accordingly. We
expect perhaps a few more results can be obtained with this substitution.

Second, Lemma 1 has a stronger version:

######  Lemma 12.

[PST03] Any minimal counterexample to HC-$\\{\overline{K_{3}}\\}$ has no
connected dominating matching.

Here, a connected matching is a set of vertex-disjoint edges that are pairwise
adjacent. It is dominating if additionally every vertex outside the matching
is adjacent to every edge in the matching. A dominating edge is just a
connected dominating matching with one edge. This substitution theoretically
allows you to sidestep Theorem 7, especially the restriction on
$\overline{C_{4}}$-cores; for instance it was the main ingredient used to
prove that HC-$\\{\overline{K_{3}},H_{7}\\}$ holds in [PST03]. It is clear how
to extend Algorithm 1 to incorporate this stronger result. However, it is not
immediately clear how to reconcile it with Algorithm 2/3, since it is
conjectured:

######  Conjecture 2.

All $\overline{K_{3}}$-free graphs on $n$ vertices have a set of $\lceil
n/2\rceil$ pairwise adjacent vertices or edges.

This conjecture is called Seymour’s Strengthening of
HC-$\\{\overline{K_{3}}\\}$ in [Bla07] or the matching version of
HC-$\\{\overline{K_{3}}\\}$ in [CS12]. It is very close to conjecturing that
all $\overline{K_{3}}$-free graphs have a connected dominating matching (which
is a slightly stronger statement), so at the very least one should expect
“most” $\overline{K_{3}}$-free graphs to have a connected dominating matching.
Thus, naïvely replacing the check for dominating edges with a check for
connected dominating matchings likely completely removes the impact of
Algorithms 2 and 3.

Third, if one marks vertices in the graph and only checks for subgraphs
containing the set of marked vertices, rather than subgraphs in the whole
graph, one can prove theorems of the form “In any minimal counterexample to
HC-$\\{\overline{K_{3}}\\}$, every induced $G$ must be part of an induced
$G^{\prime}$” where $G^{\prime}$ contains $G$ as an induced subgraph. For
example:

######  Theorem 8.

In any minimal counterexample to HC-$\\{\overline{K_{3}}\\}$, every vertex
must be found in some induced $C_{5}$.

###### Proof.

Suppose $G$ is a minimal counterexample to HC-$\\{\overline{K_{3}}\\}$. Let
$a$ be an arbitrary vertex to $G$. Obviously $a$ must have a nonneighbor $c$,
and $G$ must be connected so we may take $c$ to be adjacent to a neighbor of
$a$, say $b$. The edge $ab$ is not a dominating edge, so there is a vertex $d$
adjacent to neither $a$ nor $b$; this vertex must be adjacent to $c$ to avoid
$\overline{K_{3}}$. Then for $bc$ to not be a dominating edge, there is a
vertex $e$ adjacent to neither $b$ nor $c$; this vertex must be adjacent to
$a$ and $d$. Then $\\{a,b,c,d,e\\}$ is an induced $C_{5}$ containing $a$. ∎

In a future paper, we will modify the algorithms in this paper to obtain many
more results like the one above and also incorporate the stronger versions of
Lemmas 1 and 3.

##  5 Acknowledgements

This work was supported by funding from Princeton University for undergraduate
independent projects. Thank you to Maria Chudnovsky, Paul Seymour, Zach
Hunter, and Jan Goedgebeur for helpful comments on the paper and work.

## References

  * [BGSP12] Gunnar Brinkmann, Jan Goedgebeur, and Jan-Christoph Schlage-Puchta.  Ramsey numbers R(K3,G) for graphs of order 10.  The Electronic Journal of Combinatorics, 19(4), 2012.
  * [Bla07] Jonah Blasiak.  A special case of Hadwiger’s conjecture.  Journal of Combinatorial Theory, Series B, 97(6):1056–1073, 2007\.
  * [Bos19] Christian Bosse.  A note on Hadwiger’s conjecture for $W_{5}$-free graphs with independence number two.  Discrete Mathematics, 342, 2019.
  * [CN06] Gabor Csardi and Tamas Nepusz.  The igraph software package for complex network research.  InterJournal, Complex Systems:1695, 2006.
  * [CS12] Maria Chudnovsky and Paul Seymour.  Packing seagulls.  Combinatorica, 32:251–282, 2012.
  * [HSS08] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart.  Exploring Network Structure, Dynamics, and Function using NetworkX.  In Gaël Varoquaux, Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11 – 15, Pasadena, CA USA, 2008.
  * [IMM18] Alexey Ignatiev, Antonio Morgado, and Joao Marques-Silva.  PySAT: A Python toolkit for prototyping with SAT oracles.  In SAT, pages 428–437, 2018.
  * [JR95] Tommy Jensen and Gordon Royle.  Small graphs with chromatic number 5: A computer search.  Journal of Graph Theory, 19(1):107–116, 1995.
  * [Kri10] Matthias Kriesell.  On Seymour’s strengthening of Hadwiger’s conjecture for graphs with certain forbidden subgraphs.  Discrete Mathematics, 310:2714–2724, 2010.
  * [McK] Brendan McKay.  Combinatorial data.  http://users.cecs.anu.edu.au/~bdm/data/ramsey.html.
  * [PST03] Michael D. Plummer, Michael Stiebitz, and Bjarne Toft.  On a special case of Hadwiger’s conjecture.  Discussiones Mathematicae Graph Theory, 23:333–363, 2003.
  * [Ran04] Bert Randerath.  3-Colorability and forbidden subgraphs. I: Characterizing pairs.  Discrete Mathematics, 276(1):313–325, 2004.  6th International Conference on Graph Theory.
  * [Sey16] Paul Seymour.  Hadwiger’s conjecture.  In Open Problems in Mathematics, pages 417–437, 2016.
  * [SWY21] Joshua Schroeder, Zhiyu Wang, and Xingxing Yu.  On the 3-colorability of triangle-free and fork-free graphs, 2021.

##  Appendix A Further Implementation Details and Code

Graph computations were done using the igraph Python package ([CN06]). In many
places one must check if a graph has a particular induced subgraph (either
$\overline{K_{3}}$ for the independence number 3 checks, or some given graph
$H$ for the the property $P$ checks whenever $P$ is the property of containing
an induced $H$). This problem is NP-complete, but it can be solved quickly
enough for small graphs such as ours. In our case, we used igraph’s
implementation of the LAD algorithm.

To perform the check for a four-clique cover of $G$ at the end of Algorithm 2,
we model it as a sat instance and use a sat solver. Specifically, there are
four variables $v_{1}$, $v_{2}$, $v_{3}$, $v_{4}$ for each vertex $v$ in $G$
corresponding to the four cliques that $v$ can be included in. The boolean
formula is the conjunction of the following clauses:

  * •

$(v_{1}\vee v_{2}\vee v_{3}\vee v_{4})$ for each $v\in V(G)$, ensuring that
$Q_{1},Q_{2},Q_{3},Q_{4}$ cover $G$;

  * •

$(\neg v_{i}\vee\neg u_{i})$ for each $uv\in E(G)$ and $i=1,2,3,4$, ensuring
that $Q_{1},Q_{2},Q_{3},Q_{4}$ are cliques;

  * •

$(\sum_{i=1}^{4}\sum_{v\in V(H)}v_{i}\geq\lvert H\rvert+2)$, ensuring the
additional condition $\sum_{i=1}^{4}\lvert Q_{i}\cap V(H)\rvert\geq\lvert
H\rvert+2$.

We used PySAT ([IMM18]) to solve these sat instances.

Also, often one needs to generate the set of graphs formed by adding one
vertex $v$ to a graph $H$ with some restrictions on the result. Instead of
trying to add $v$ to $H$, we instead start with $v$ and then add the vertices
of $H$ one at a time, at each step checking the imposed restrictions. This
allows one to “bail out early,” so to speak, if a potential attachment does
not satisfy the restrictions. Some care must be taken afterwards to fix the
vertex labelings so that $H$ gets labels 1 through $\lvert V(H)\rvert$ and $v$
gets label $\lvert V(H)\rvert+1$.

Finally, much computation can be reused when running Algorithm 3 with the same
input aside from $k$. In fact, the sets $A$, $B$, and $C$ are the same
regardless of $k$, so we temporarily cache them whenever Algorithm 4 reaches
the part where Algorithm 3 should be run.

We provide code at https://github.com/dcartermath/hc-forbidden-subgraphs which
can be used to verify Theorem 2. We used Python version 3.9.6, igraph version
0.9.11, and PySAT version 0.1.7.dev19, though the code most likely works fine
with newer versions. The program reads the TeX source of Figures 3, 4, and 5,
respectively copied into files `hp_figure`, `i_figure`, and `edges_figure` put
in the same directory as this program, to determine the graphs, labelings, and
steps to verify Theorem 2, thus making absolutely sure that the data provided
in the main body of this paper is correct. Each line of output is one arrow of
Figure 5 consisting of the name of the input graph, the name of the output
graph, the total number of graphs ever added to the set $A$, and the weight.

In the process of discovering Theorem 2, we did not immediately use the
optimizations discussed above. Initially, we simply brute-force checked for
four-clique covers with the desired properties, and computed the set of graphs
formed by adding a single vertex to a given graph $H$ by simply trying all
$2^{\lvert V(H)\rvert}$ possibilities for the neighbor set of the new vertex.
Whenever we made an optimization, we verified the newer version gave an
identical state to the older version run for one hour. Thus, we are confident
in the correctness of our implementation.

##  Appendix B More Data

Running the code in Appendix A, after some minutes or hours of computation,
produces the following output:

    K23c I4 2 544
    K7 H2p 121 317568
    W5 I3 5 832
    H7 I15 2 640
    K7 H3p 600 6222976
    H7 I2 2 640
    I2 I12 4 576
    I15 I18 27 194688
    I3 I14 1 64
    H2p H1p 532 2454144
    I4 H5p 26 423488
    I18 I25 1 128
    H5p I26 65 324736
    I14 I21 2 384
    I12 I1 7 5248
    I1 I13 2 192
    I25 I5 336 3440896
    I26 H33p 348 20723968
    I25 H24p 134 715008
    I21 I6 20 42752
    I25 I8 76 527616
    I21 I11 33 102144
    I21 H16p 139 768768
    I21 I19 35 84736
    I19 H21p 121 336128
    I5 H13p 524 7547520
    I13 I7 17 19584
    I11 H20p 73 407168
    H24p I22 522 3486976
    H24p I16 95 604928
    H24p I23 989 22616320
    H24p H26p 136 611072
    I6 I20 32 28800
    I8 H12p 131 411776
    I7 H18p 112 345216
    I23 H32p 1 256
    I20 H31p 45 1067776
    I22 H29p 333 6226688
    I16 I24 1 128
    H31p H4p 338 5561856
    I24 H25p 1348 15871232
    H18p H14p 566 14731520
    I24 H27p 94 621824
    H18p I10 265 1639680
    I10 H7p 256 1474432
    I10 H17p 218 1423232
    H27p I17 354 8121088
    I10 H15p 265 11495296
    I10 H8p 756 10430336
    H27p H30p 327 9972480
    H4p H10p 899 10312832
    I10 H9p 305 1976192
    H15p H23p 479 15760640
    I17 H28p 1 128
    H17p H11p 341 1031424
    H7p I9 369 3561216
    H23p H6p 723 13390592
    I9 H19p 19 8320
    H23p H22p 74 17303296

The four columns here separated by spaces are the in-vertex $G$ and out-vertex
$H$ of an arrow of Figure 5, then the total number of graphs added to $A$ when
Algorithm 4 is run with input $(G,H)$, and finally the weight of the arrow,
which is the sum over $H^{\prime}$ ever added to $A$ of $2^{\lvert
V(H^{\prime})\rvert}$.

##  Appendix C Proving HC-$\\{\overline{K_{3}},K_{8}\\}$

As we mentioned in the introduction, Theorem 2 is no help for proving Theorem
3 because all 477142 $\\{\overline{K_{3}},K_{8}\\}$-free graph on 27 vertices
contains all $H_{i}^{\prime}$, and $K_{7}$ and $H_{7}$. However, the vast
majority of these graphs have a dominating edge, and it turns out that the
ones that don’t have a connected dominating matching with two edges.
Specifically:

######  Proposition 2.

Of the 477142 $\\{\overline{K_{3}},K_{8}\\}$-free graph on 27 vertices, 455344
have a dominating edge and the remaining 21798 have a connected dominating
matching of two edges.

Code to verify this is available at https://github.com/dcartermath/hc-
forbidden-subgraphs. This code, `k8.py`, simply checks each graph in turn,
using the file containing such graphs available at [McK] (though note that the
relevant file contains all $\\{K_{3},\overline{K_{8}}\\}$-free graph on 27
vertices, so we must take the complement of them). The graph data is parsed
using NetworkX version 2.8.3 ([HSS08]), but the graphs are immediately
converted to igraph. The program outputs several lines of intermediate
computation before eventually the line `477142 / 477142 [455344, 21798]`,
indicating that all 477142 graphs were read, 455344 have a dominating edge,
and the remaining 21798 have a connected dominating matching of two edges.

The check for connected dominating matchings of two edges is simply hard-coded
in; a pair of edges $uv,xy$ is a connected dominating matching if all of the
following conditions are met:

  * •

$\\{u,v\\}$ and $\\{x,y\\}$ are disjoint.

  * •

$\\{u,v\\}\cap N(x)\neq\varnothing$ or $\\{u,v\\}\cap N(y)\neq\varnothing$.

  * •

For each $z\in V(G)\setminus\\{u,v,x,y\\}$, $z\in N(u)$ or $z\in N(v)$, and
$z\in N(x)$ or $z\in N(y)$.

Theorem 3 follows from Proposition 2 due to Lemma 12 and the fact that
HC-$\\{\overline{K_{3}},K_{7}\\}$ holds. The latter fact implies (similarly to
the reasoning in Corollary 1) that any counterexample to
HC-$\\{\overline{K_{3}}\\}$ has at least 27 vertices. Thus the graphs
considered in Proposition 2 either satisfy Hadwiger’s Conjecture or are
minimal counterexamples.