greater than $3$ there is an $H_{2}$ with middle path $u,s,v$ (note that there
cannot be an edge from $u$ to the neighbour $d$ of $v$ along the path to $w$,
by our original minimal choice of the path along $u,v,w$). Suppose
$u^{\prime\prime}$ has no neighbours outside of $\\{u,u^{\prime},s,v\\}$
(noting that there might be an edge from $u^{\prime\prime}$ to $v$). Then $v$
is a cut vertex. Note that none of the paths emanating from $w$ and not going
through $v$ can have vertices of degree greater than $2$, unless they are part
of a squash racket whose distinguished vertex is identified with $w$, as we
would introduce an $H_{2i}$. The case of the squash racket can be dealt with
just like the case of an even cycle so we do not concern ourselves with it
specially. Note however that there can be only one squash racket attached at
$w$ and if there is a squash racket there can be no additional even cycles or
paths attached at $w$. If the edge $u^{\prime\prime}$ to $v$ exists then there
can be no new neighbours of $u^{\prime\prime}$ without introducing an $A$ as a
subgraph. This places us in the case shown in Figure 18, and the figure shows
a star $3$-colouring in this case.

Suppose now that $u^{\prime\prime}$ has a neighbour outside
$\\{u,u^{\prime},s,v\\}$ which we call $t$ (noting that in this case there can
be no edge from $u^{\prime\prime}$ to $v$ since then there would be three
consecutive $3^{+}$ vertices). Let us continue expanding from $t$ along some
path away from $u^{\prime\prime}$ which we enumerate $t=t_{1},t_{2},\ldots$.
Suppose no such path like this reaches $w$ (or $v$) avoiding $u$. Note that
such a path cannot now arrive at either $v$ or $s$ since we have uncovered all
of their neighbours (if $v$ had more neighbours then there would be an $H_{2}$
with central path $u,s,v$). If one of the vertices $t_{j}$ has degree greater
than $2$ then we have a $H_{2i}$ involving a central path either from $t_{j}$
to $v$ via $u$ or from $t_{j}$ to $w$ via $u$. Thus we have nothing more than
a path here which must terminate at some $t_{k}$. This case will be superseded
by a more general case which will come later (see Figure 20).

Suppose we have a path $t_{1},t_{2},\ldots$ that eventually joins the path
between $v$ and $w$ exclusive of $v$ and $w$. Then we contradict minimality of
the path from $u$ to $w$ via $v$. Thus we have a path $t_{1},t_{2},\ldots$
that eventually joins $w$. (Possibly it did so via, w.l.o.g.,
$w^{\prime\prime}$.) This path must be of odd length since otherwise it would
produce an $H_{2i}$. If any vertex on this path has degree greater than $2$
then it induces some $H_{2i}$ on a path to either $u$ or $w$. Except in the
case that it is distance $2$ from $w$, an odd distance from $u$, and shares
two neighbours with $w$ (and these are $w$’s only neighbours). This case is
drawn in Figure 19. Therefore, there is nothing but this path, except that we
did not isolate the degree of $w$. Indeed, $w$ may have arbitrarily high
degree. Any path emanating from $w$ and not eventually reaching $v$ (we have
accounted for all such paths) may not have a vertex $c$ of degree greater than
$2$, since otherwise this vertex would produce an $H_{2i}$ with middle path to
either $w$ or $v$. Except in the case that $c$ is at distance $2$ from $w$ and
shares two neighbours the two neighbours $w^{\prime}$ and $w^{\prime\prime}$
with $w$, in which case $c$ may have a path emanating from it in the form of
$c=c_{1}$, $c_{2}$, etc. This case, in which there is a squash racket with
distinguished vertex identified with $w$, will be superseded by the next. Note
however that there can be only one squash racket attached at $w$ and if there
is a squash racket there can be no additional even cycles or paths. It follows
then that some path may leave $w$ and terminate in a vertex of degree $1$, or
return to $w$ producing a cycle of even length. We claim the graph $G$ is a
yes-instance of star $3$-colouring. Let us refer to Figure 20.

$\textstyle{u^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{w^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{u\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{s\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{v\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{path}}$$\scriptstyle{\mathit{odd}}$-----$\textstyle{w\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{even}}$--$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{even}}$$\textstyle{u^{\prime\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{w^{\prime\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{w^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{path}}$$\scriptstyle{\mathit{odd}}$-----$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{even}}$--$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{even}}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{w^{\prime\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$
$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$etc.$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$

|
---|---
$\textstyle{u^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{w^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{u\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{s\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{v\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{path}}$$\scriptstyle{\mathit{odd}}$----$\textstyle{w\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$etc.$\textstyle{u^{\prime\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{w^{\prime\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

Figure 18: The second cut vertex case of Lemma E.81 with its star
$3$-coloring. There may be a squash racket attached at $w$ instead of even
cycles or paths. The squash racket case is drawn on the bottom. For the
colouring around $w$ we draw to the left the possible colours that may appear
to the left and we draw to the right two paths that need to be identified to
make an even cycle of squash racket (middle right).

$\textstyle{u^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{u\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{odd}}$$\scriptstyle{\mathit{path}_{2}}$--------$\textstyle{s\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{v\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{odd}}$$\scriptstyle{\mathit{path}_{1}}$-----$\textstyle{w\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{t_{k}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$-----$\textstyle{w^{\prime\prime}}$$\textstyle{w^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{odd}}$$\scriptstyle{\mathit{path}_{2}}$--------$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{odd}}$$\scriptstyle{\mathit{path}_{1}}$-----$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$-----$\textstyle{1}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{\mathit{path}_{1}}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$
$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2}$$\textstyle{\mathit{path}_{2}}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2}$

Figure 19: The middle case of Lemma E.81 with its star $3$-coloring (above).
One could think of this as a squash racket with distinguished vertex
identified with $w$ in which the path continues and actually reaches $u$. The
concurrent star $3$-colouring of $\mathit{path}_{1}$ and $\mathit{path}_{2}$
is given below.

$\textstyle{u^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{w^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{u\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{s\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{v\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{odd}}$$\scriptstyle{\mathit{path}_{1}}$-----$\textstyle{w\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{even}}$--$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{even}}$$\textstyle{u^{\prime\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{t\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{odd}}$$\scriptstyle{\mathit{path}_{2}}$--------$\textstyle{w^{\prime\prime}}$
$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{w^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{odd}}$$\scriptstyle{\mathit{path}_{1}}$-----$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{even}}$--$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{even}}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathit{odd}}$$\scriptstyle{\mathit{path}_{2}}$--------$\textstyle{w^{\prime\prime}}$

---
$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$
$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$etc.$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$

$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$
$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$etc.$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$

Figure 20: The coup de grâce of Lemma E.81 with its star $3$-coloring (above).
The concurrent star $3$-colouring of $\mathit{path}_{1}$ and
$\mathit{path}_{2}$ (middle left) and any even cycles or squash rackets
(middle right, merge top and bottom paths to form even cycle or squash
racket). At the bottom is the special case where both paths have length
$1\bmod 3$ in which case $w$ is coloured $2$.

Recall that $\overline{\alpha P_{i}+\beta P_{j}}$ is the graph obtained from
the disjoint union of $\alpha$ paths $P_{i}$ and $\beta$ paths $P_{j}$, where
one end from all the paths are identified as a single vertex $u$ and the other
ends from all the paths are identified as a single vertex $v$.

######  Lemma E.83.

$\overline{2P_{4}+3P_{6}}$ cannot be star $3$-coloured.

######  Proof E.84.

Assume otherwise. Let $x_{1}$ be the neighbour of $u$ on one copy of $P_{4}$
and $x_{2}$ the neighbour of $v$ on this path. Similarly, let $y_{1}$ be the
neighbour of $u$ on the second copy of $P_{4}$ and $y_{2}$ the neighbour of
$v$. Label the internal vertices of the first copy of $P_{6}$ $z_{1}\dots
z_{4}$ where $z_{1}$ is the neighbour of $u$ and $z_{4}$ is the neighbour of
$v$. Let $w_{1}\dots w_{4}$ be the internal vertices of the second copy of
$P_{6}$ such that $w_{1}$ is adjacent to $u$ and $w_{4}$ is adjacent to $v$.

First consider a proper star $3$-colouring $c$ in which $u$ and $v$ are
coloured differently, say $u$ is coloured $1$ and $v$ is coloured $2$. It must
be that either $c(x_{1})=2$ or $c(x_{2})=1$. Without loss of generality,
$c(x_{1})=2$. Then $c(x_{2})=3$. Every remaining neighbour $a$ of $v$ then has
colour $1$, else we have a bichromatic $P_{4}$ with vertex set
$\\{a,v,x_{2},x_{1}\\}$. To avoid a bichromatic $P_{4}$, $c(y_{1})=3$. Each
further neighbour $b$ of $u$ then has colour $2$, else we have a bichromatic
$P_{4}$ with vertex set $\\{b,u,y_{1},y_{2}\\}$. We now consider the first
copy of $P_{6}$. Since $c(z_{1})=2$, $c(z_{2})=3$, else there is a bichromatic
$P_{4}$ with vertex set $\\{x_{1},u,z_{1},z_{2}\\}$. However, $c(z_{3})=3$,
else we have a bichromatic $P_{4}$ with vertex set
$\\{z_{3},z_{4},v,y_{2}\\}$. This leaves two adjacent vertices coloured $3$, a
contradiction.

Therefore, $u$ and $v$ must be coloured alike in any proper star $3$-colouring
$c$. Without loss of generality, they are both assigned colour $1$. Without
loss of generality, $c(x_{1})=2$ and $c(x_{2})=3$. Now consider the first copy
of $P_{6}$. First assume that $c(z_{1})=2$. Then, to avoid a bichromatic
$P_{4}$ with vertex set $\\{z_{2},z_{1},u,x_{1}\\}$, $c(z_{2})=3$. Now, to
avoid a bichromatic $P_{4}$ along this path, at least one of $z_{3}$ and
$z_{4}$ must be coloured $2$. If $c(z_{3})=2$ then $c(z_{4})=3$ and we have a
bichromatic $P_{4}$. Therefore, $c(z_{4})=2$ and $c(z_{3})=1$. Each remaining
neighbour of $v$ then has colour $3$ to avoid a bichromatic $P_{4}$. Since
$c(w_{4})=3$, $c(w_{3})=2$, else we have a bichromatic $P_{4}$. If
$c(w_{2})=3$, then $c(w_{1})=2$ and we have a bichromatic $P_{4}$ on
$\\{w_{1},w_{2},w_{3},w_{4}\\}$. Thus, $c(w_{2})=1$, whereupon $c(w_{1})=3$ to
avoid a bichromatic $P_{4}$ on $\\{x_{1},u,w_{1},w_{2}\\}$. The same arguments
apply to the third copy of $P_{6}$ but now we have a bichromatic $P_{4}$ on
$1313$ with vertex set $\\{u,w_{1},w_{2}\\}$ plus the first vertex on the
third copy of $P_{6}$, a contradiction.

It remains to consider the case where $c(z_{1})=3$. If $c(z_{2})=1$ then
$c(z_{3})=2$ and $c(z_{4})=3$. Additionally, every remaining neighbour $c$ of
$u$ is coloured $2$ to avoid a bichromatic $P_{4}$ with vertex set
$\\{z_{2},z_{1},u,c\\}$. It must then be that $c(w_{1})=2,c(w_{2})=3$. In
fact, this case is covered in the previous paragraph by an automorphism of
$\overline{2P_{4}+3P_{6}}$ that swaps $u$ and $v$, as well as colours $2$ and
$3$. Therefore $c(z_{2})=2$. To avoid a bichromatic $P_{4}$ along this copy of
$P_{6}$, $c(z_{3})=1$. Now $c(z_{4})=2$ since otherwise we have a bichromatic
$P_{4}$ with vertex set $\\{z_{3},z_{4},v,x_{2}\\}$. However, this induces a
bichromatic $P_{4}$ with vertex set $\\{z_{2},z_{3},z_{4},v\\}$, a
contradiction.

######  Lemma E.85.

Let $G$ be a bipartite connected $(H_{2},H_{4},\ldots)$-subgraph-free graph
with two vertices of degree greater than two. Then $G$ can be star
$3$-coloured unless it contains one of $\mathbb{A}$ or
$\overline{2P_{4}+3P_{6}}$ as a subgraph.

######  Proof E.86.

Let the two $3^{+}$ vertices be $u$ and $v$. There may be many paths from $u$
to $v$. Suppose one of these paths is of even length. Then, as $G$ is
bipartite, they must all be of even length. There may further be even cycles
attached to $u$ and even cycles attached to $v$. In order to avoid $H_{2i}$,
the number of these paths between $u$ and $v$ must be bounded, in particular,
there can be no more than one path of length greater than or equal to $4$. See
Figure 21 for the $3$-star colouring in this case.

Suppose, one of the paths between $u$ and $v$ is of odd length. Then they must
all be of odd length. (There may further be even cycles attached to $u$ and
even cycles attached to $v$.) Suppose there are paths between $u$ and $v$ of
length both $1$ and $3$. Now, $u$ and $v$ must have third neighbours
$u^{\prime}$ and $v^{\prime}$, respectively, that are not involved in these
paths (e.g., by bipartiteness). Since $u^{\prime}\neq v^{\prime}$, again by
bipartiteness, we have an $\mathbb{A}$ as a subgraph and this is a no-
instance.

Now we consider three cases. Firstly, that there is a path of length $1$ and
all other paths are of length at least $5$ (see Figure 22). Secondly, that all
paths are of length at least $3$ and there are at most two paths of length $5$
(see Figure 23). Thirdly, that all paths are of length at least $3$ and there
is at most one path of length $3$ (see Figure 24).

---
$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
Figure 21: The first case of Lemma E.85 with its star $3$-coloring. At the top
and bottom the paths may be made into even cycles by the identification of two
vertices. Note there is a $313$ down the path of length $4$ which would cause
a problem were we to have another one, but we already explained this would
introduce an even $H_{2i}$.
$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
Figure 22: The case from Lemma E.85 in which there is path from $u$ to $v$ of
length $1$ with its star $3$-coloring. At the top and bottom the paths may be
made into even cycles by the identification of two vertices.
---
$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
Figure 23: The case of Lemma E.85 in which, from $u$ to $v$, there are no
paths of length $1$ and at most two paths of length $5$, with its star
$3$-coloring. There may be more paths of length $2$ between $u$ and $v$ but no
more paths of length $5$. At the top and bottom the paths may be made into
even cycles by the identification of two vertices.
---
$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2}$$\textstyle{1}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
Figure 24: The final case of Lemma E.85 in which, from $u$ to $v$, there are
no paths of length $1$ and at most one path of length $3$, with its star
$3$-coloring.

Let us recall the following corrollary which we are now ready to prove.

Corollary 5.38. A bipartite connected
$(\mathbb{H}_{2},\mathbb{H}_{4},\ldots)$-subgraph-free graph is a yes-instance
to Bipartite Star $3$-Colouring unless it contains $\mathbb{A}$ or
$\overline{2P_{4}+3P_{6}}$. Therefore, Bipartite Star $3$-Colouring on
$(\mathbb{H}_{2},\mathbb{H}_{4},\ldots)$-subgraph-free graphs is in P.

######  Proof E.87.

The first part follows from the combination of Lemma E.81 and Lemma E.85 (note
that the case in which there is only one or no $3^{+}$-vertex is covered a
fortiori in the latter). The algorithm checks for $\mathbb{A}$ or
$\overline{2P_{4}+3P_{6}}$ as a subgraph which plainly can be done in
polynomial time.

###  E.2 Many $3^{+}$-vertices

Recall that a diamond is a $C_{4}$ with a chord. Let _diamond-with-pendant_ be
built from a diamond, with a pendant vertex added to a vertex of degree $2$.
The diamond-with-pendant involves a $C_{4}$ with three $3^{+}$-vertices. Let
$\mathbb{F}_{0}$ comprise of the following graphs: $\mathbb{A}$, $C_{5}$ and
bowtie.

######  Lemma E.88.

Let $G$ be a connected graph with at least five $3^{+}$-vertices. Either $G$
contains some $H_{2i}$ as a subgraph or contains some graph from
$\mathbb{F}_{0}$ as a subgraph or contains some $C_{4}$ with (at least) three
$3^{+}$ vertices.

######  Proof E.89.

We will essentially follow the proof of Lemma E.81 to show that, if we assume
there are three $3^{+}$-vertices, we can never uncover more than one more,
unless $G$ contains some $H_{2i}$ as a subgraph or contains $\mathbb{A}$ as a
subgraph or contains some $C_{4}$ with (at least) three $3^{+}$ vertices. Of
course, as we follow the proof of Lemma E.81, we can no longer use
bipartiteness. This means we have an important new case at the start (later on
we only used it to assume that certain cycles were even).

Suppose there are three consecutive $3^{+}$-vertices $u,v,w$ in a clique (the
“triangle”). Suppose any two of these have a common neighbour, then the graph
is not star $3$-colourable by Lemma E.79. Thus, they have private neighbours
$u^{\prime},v^{\prime},w^{\prime}$, respectively, that form with them the
“net”. Since $G$ is connected, there is a path from the net, w.l.o.g. through
$u^{\prime}$, to another $3^{+}$ vertex $t$. Choose such a $t$ closest to the
triangle in the net. If $t$ has two neighbours outside of the net, then there
is an $H_{2i}$ as a subgraph with central path either $t,\ldots,u$ (if
distance from $t$ to $u$ even) or either of $t,\ldots,u,v$ and $t,\ldots,u,w$
(if distance from $t$ to $u$ odd). Thus, $t$ has a neighbour in the net and we
have discovered a path from $u$ to (w.l.o.g.) $v$, avoiding $w$, with a
$3^{+}$ vertex at distance either $1$ or $2$ from $v$. Let us choose a minimal
such path (not permitting $v^{\prime}=u^{\prime}$ as we already ruled this our
by assumption). This minimal path induces a cycle in $G$. If it is $C_{4}$ or
$C_{5}$ we are in a no-instance (in both cases there is a – potentially non-
induced – $C_{5}$). W.l.o.g., assume it is of length at least $6$.

Suppose $t$ is at distance $1$ from $v$ and we may w.l.o.g. assume it is
$v^{\prime}$ itself. If $v^{\prime}$ has an edge to anywhere in the net, then
we are in a no-instance (either we have a $C_{5}$ or diamond-with-pendant).
Thus, some third neighbour $v^{\prime\prime}$ of $v^{\prime}$ is outside the
net. Now there is an $H_{2}$ with central path $v^{\prime},v,u$. Suppose $t$
is at distance $2$ from $v$. We have found two neighbours of $t$ so let
$t^{\prime}$ be a third neighbour, If $t^{\prime}$ is in the net then we are
in a no-instance with a $C_{5}$; unless $t^{\prime}=v$, in which case we were
not in a minimal cycle (essentially $v^{\prime}$ could be $t$). Thus,
$t^{\prime}$ is outside the net. Now there is an $H_{2}$ with central path
$t,v^{\prime},v$.

Now let us follow the proof as in the bipartite case (Lemma E.81) but no
longer using bipartiteness. Suppose $u,v,w$ are consecutive. Then $u$ and $w$
must have another common neighbour to avoid an $H_{2}$. Now we violate Lemma
E.79. Thus, $u,v,w$ may not be consecutive.

Suppose now that $u$ and $w$ have two common neighbours $p$ and $q$. According
to Lemma E.79, both of these have degree $2$ and neither of these may have an
edge to $v$, therefore $v$ has a distinct neighbour $z$. Suppose either $u$ or
$v$ has degree greater than $3$, w.l.o.g. $u$. Then there is an $H_{2}$ with
$u,p,w$ forming the central path. Thus, $u$ and $w$ are of degree $3$ and $v$
is a cut vertex. If either of the paths from $u$ to $v$ or $v$ to $w$ is even
then we have an $H_{2i}$. Thus we may assume both are odd. If $z$ has degree
greater than $2$ then the paths from $v$ to $u$ and $v$ to $w$ must be even to
avoid an $H_{2i}$ with central path (e.g.) $z,v,\ldots,u$. But then there is
an $H_{2i}$ with central path $v,\ldots,u$. Thus, $z$ has degree $1$ or $2$.
Indeed, we may follow a path $z=z_{1}$, $z_{2}$ etc. and never find a vertex
of degree greater than $2$, unless it returns to $v$, as it would imply either
an $H_{2i}$ with central path $z_{j},\ldots,v$ (if $j$ even) or (e.g.)
$z_{j},\ldots,v,\ldots,u$ (if $j$ is odd). Thus, either the path ends or it
returns to $v$ as a cycle. And there may be more than one such path or cycle.
In this case, $G$ has three $3^{+}$-vertices.

Suppose now that $u$ and $w$ have one common neighbour $p$ and two distinct
neighbours $u^{\prime}$ and $w^{\prime}$, respectively. Since $u,v,w$ are not
consecutive, there is an $H_{2}$ using $u,p,w$ as the central path.

Suppose now that $u$ and $w$ have neighbours $u^{\prime},u^{\prime\prime}$ and
$w^{\prime},w^{\prime\prime}$, respectively, so that these vertices are
pairwise distinct. If the total length of the path on $u,v,w$ is even then we
have some $H_{2i}$. W.l.o.g., assume the path from $u$ to $v$ is even,
whereupon the path from $v$ to $w$ must be odd. There must be an edge from $v$
to one of $u^{\prime},u^{\prime\prime}$ (w.l.o.g. $u^{\prime}$) to avoid an
$H_{2i}$. By minimality of the path $u,v,w$, the distance from $u$ to $v$
along the path we chose must be $2$ with middle vertex $s$. According to Lemma
E.79, both $s$ and $u^{\prime}$ have degree $2$ in $G$. If $u$ has degree
greater than $3$ there is an $H_{2}$ with middle path $u,s,v$ (note that there
cannot be an edge from $u$ to the neighbour $d$ of $v$ along the path to $w$,
by our original minimal choice of the path along $u,v,w$). Suppose
$u^{\prime\prime}$ has no neighbours outside of $\\{u,u^{\prime},s,v\\}$
(noting that there might be an edge from $u^{\prime\prime}$ to $v$). Then $v$
is a cut vertex. Note that none of the paths emanating from $w$ and not going
through $v$ can have vertices of degree greater than $2$, unless they are part
of a squash racket whose distinguished vertex is identified with $w$, as we
would introduce an $H_{2i}$. The squash racket case can be dealt with just
like a cycle so we do not concern ourselves with it specially. Note however
that there can be only one squash racket attached at $w$ and if there is a
squash racket there can be no additional cycles or paths. If the edge
$u^{\prime\prime}$ to $v$ exists then there can be no new neighbours of
$u^{\prime\prime}$ without introducing an $\mathbb{A}$ as a subgraph. In this
case, $G$ has three $3^{+}$-vertices.

Suppose now that $u^{\prime\prime}$ has a neighbour outside
$\\{u,u^{\prime},s,v\\}$ which we call $t$ (noting that in this case there can
be no edge from $u^{\prime\prime}$ to $v$ since then there would be three
consecutive $3^{+}$-vertices). Let us continue expanding from $t$ along some
path away from $u^{\prime\prime}$ which we enumerate $t=t_{1},t_{2},\ldots$.
Suppose no such path like this reaches $w$ (or $v$) avoiding $u$. Note that
such a path cannot now arrive at either $v$ or $s$ since we have uncovered all
of their neighbours (if $v$ had more neighbours then there would be an $H_{2}$
with central path $u,s,v$). If one of the vertices $t_{j}$ has degree greater
than $2$ then we have a $H_{2i}$ involving a central path either from $t_{j}$
to $v$ via $u$ or from $t_{j}$ to $w$ via $u$. Thus we have nothing more than
a path here which must terminate at some $t_{k}$. In this case, $G$ has three
$3^{+}$-vertices.

Suppose we have a path $t_{1},t_{2},\ldots$ that eventually joins the path
between $v$ and $w$ exclusive of $v$ and $w$. Then we contradict minimality of
the path from $u$ to $w$ via $v$. Thus we have a path $t_{1},t_{2},\ldots$
that eventually joins $w$. (Possibly it did so via, w.l.o.g.,
$w^{\prime\prime}$.) This path must be of odd length since otherwise it would
produce an $H_{2i}$. If any vertex on this path has degree greater than $2$
then it induces some $H_{2i}$ on a path to either $u$ or $w$. Except in the
case that it is distance $2$ from $w$, an odd distance from $u$, and shares
two neighbours with $w$ (and these are $w$’s only neighbours). In this case,
$G$ has four $3^{+}$-vertices.

Therefore, there is nothing but this path, except that we did not isolate the
degree of $w$. Indeed, $w$ may have arbitrarily high degree. Any path
emanating from $w$ and not eventually reaching $v$ (we have accounted for all
such paths) may not have a vertex $c$ of degree greater than $2$, since
otherwise this vertex would produce an $H_{2i}$ with middle path to either $w$
or $v$. Except in the case that $c$ is at distance $2$ from $w$ and shares two
neighbours the two neighbours $w^{\prime}$ and $w^{\prime\prime}$ with $w$, in
which case $c$ may have a path emanating from it in the form of $c=c_{1}$,
$c_{2}$, etc. This case, in which there is a squash racket with distinguished
vertex identified with $w$, will be superseded by the next. Note however that
there can be only one squash racket attached at $w$ and if there is a squash
racket there can be no additional cycles or paths. It follows then that some
path may leave $w$ and terminate in a vertex of degree $1$, or return to $w$
producing a cycle. In this case, $G$ has three $3^{+}$-vertices.

######  Lemma E.90.

Let $d$ be a fixed constant. Suppose $G$ contains at most $d$
$3^{+}$-vertices. Then Star $3$-Colouring (restricted to such graphs) can be
solved in polynomial time.

######  Proof E.91.

Let us give the proof for $d=2$ where there are exactly two $3^{+}$-vertices
before we make the obvious generalisation. Let $u$ and $v$ be the
$3^{+}$-vertices. Let $P_{x}$ be the set of paths from $x\in\\{u,v\\}$ that
terminate with a vertex of degree $1$. Let $C_{x}$ be the set of paths from
$x\in\\{u,v\\}$ that return to $x$ making a cycle. Let $P_{u,v}$ be the set of
paths from $u$ to $v$. These account for all vertices of $G$. Recall that star
colouring has the property that it can see up to distance $3$ from a certain
vertex in terms of the effect of colours. Consider the paths in $P_{u,v}$ that
are of length $\geq 3+4+3=10$. In any star $3$-colouring of a path of length
$\geq 10$, the middle four vertices must contain a consecutive run of three
distinct colours. It follows that a path of length $10$ covers all longer
paths of length $1\bmod 3$. Then, paths of length $11$ and $12$ cover all
longer paths of length $2$ and $0\bmod 3$, respectively. Thus, we may w.l.o.g.
consider that the paths in $P_{u,v}$ are of length at most $12$. Now, suppose
there are more than $N=3^{6}$ of some particular length $m$ of path. Then in
any star $3$-colouring of these, some sequence of three colours at the
beginning and at the end must appear more than once. Since it appears more
than once it could be repeated if there were additional paths of length $m$
over and above the $N$ without violating the condition of star $3$-colouring.
In this fashion, we may assume that there are at most $3^{6}$ copies of a path
of any length. But now we reduced our graph to one of bounded size $\leq
5\cdot 12\cdot 12\cdot 3^{6}$ (this is: #sets, #path-lengths, #vertices, #end-
types, respectively) and we can check using brute force whether it is star
$3$-colourable.

Now, when $d$ is larger, we consider $P_{x},C_{x},P_{x,y}$ for all vertices
$x$ and $y$ giving a quadratic number in $d$ of sets to consider. The same
bound on the length of paths applies as in the case $d=2$. The argument again
reduces any graph to a graph of size at most $f(d)$ for some function $f$
which is $O(d^{2})$ and the result follows.

Let us recall the principal result of this section.

Corollary 5.39. Star $3$-Colouring on $(H_{2},H_{4},\ldots)$-subgraph-free
graphs is in P.

######  Proof E.92.

If there are more than four-$3^{+}$ vertices then we look for a subgraph that
is either in $\mathbb{F}_{0}$ or a $C_{4}$ with more than two
$3^{+}$-vertices, as per Lemma E.88. Else, we use the brute force approach of
Lemma E.90.

$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet}$
$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet}$

$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\bullet}$

Figure 25: Some important minimal no-instances for Star $3$-Colouring From top
left, lexicographically: $\mathbb{A}$, $\overline{2P_{4}+3P_{6}}$, $C_{5}$ and
diamond-with-pendant. The graph at the bottom did not appear in our exposition
but is a fascinating example which goes some way to explain why we still have
no forbidden subgraphs characterisation for the general case.

##  Appendix F Bipartite Star $3$-Colouring is a C12-problem

Figure 26: A star $3$-colouring of the graph $G^{\prime}$ obtained from a
$3$-colouring of $G=K_{3}$. Only part of $G^{\prime}$ is displayed.

######  Lemma F.93.

For every $g\geq 3$, Star $3$-Colouring is NP-complete for planar bipartite
graphs of girth at least $g$ and maximum degree $3$.

######  Proof F.94.

Let us begin with the proof from [6], that Star $3$-Colouring is NP-complete
for planar graphs of girth at least $g$ and maximum degree $3$, before
explaining how to finesse the result with the additional assumption of
bipartiteness.

We reduce from $3$-Colouring, which is NP-complete even for planar graphs with
maximum degree 4 [13]. Let $G$ be an instance of this restricted version of
$3$-Colouring. The vertex gadget $V$ contains

  * •

a cycle of length $12g$ with vertices $d_{1},\ldots,d_{12g}$,

  * •

$12g$ independent vertices $e_{1},\ldots,e_{12g}$ such that $e_{i}$ is
adjacent to $d_{i}$ for every $1\leq i\leq 12g$, and

  * •

four independent vertices $f_{1},f_{2},f_{3},f_{4}$ such that $f_{i}$ is
adjacent to $e_{3ig}$ for every $1\leq i\leq 4$.

We construct an instance $G^{\prime}$ of Star $3$-Colouring from $G$ as
follows. We consider a planar embedding of $G$ and for every vertex $x$, we
order the neighbours of $x$ in a clockwise way. Then we replace $x$ by a copy
$V_{x}$ of $V$. Now for every edge $mn$ of $G$, say $n$ is the $i^{th}$
neighbour of $m$ and $m$ is the $j^{th}$ neighbour of $n$, we add the edge
between the vertex $f_{i}$ of $V_{m}$ and the vertex $f_{j}$ of $V_{n}$, see
Figure 26.

It is not hard to check that in every star $3$-colouring of $V$, the four
vertices $f_{i}$ get the same colour. Moreover, there is no bichromatic path
between any two vertices $f_{i}$.

Suppose that $G$ admits a $3$-colouring $c$ of with colours in $\\{0,1,2\\}$.
For every vertex $x$ in $G$, we assign $c(x)$ to the vertices $f_{i}$ in
$V_{x}$ and we assign $(c(x)+1)\pmod{3}$ to the vertices $e_{3ig}$. Then we
extend this pre-colouring into a star $3$-colouring of $V_{x}$. This gives a
star $3$-colouring of $G^{\prime}$. Given a star $3$-colouring of
$G^{\prime}$, we assign to every vertex $x$ in $G$ the colour of the vertices
$f_{i}$ in $V_{x}$, which gives a $3$-colouring of $G$.

Finally, as $G$ is planar with maximum degree $4$, it holds that $G^{\prime}$
is planar with maximum degree $3$. Moreover, by construction, $G^{\prime}$ has
girth at least $g$.

Now, in general $G^{\prime}$ is not bipartite. Consider the point where we
translate edges arising in $G$ to edges between some $f_{i}$ and $f_{j}$ in
$G^{\prime}$. Without loss of generality, let $g$ be even and let
$g^{\prime}=g+1$ be odd. Suppose we first augment a new copy of the vertex
gadget $V^{\prime}$, of girth $12g^{\prime}$, with $f_{i}$ identified with
$f^{\prime}_{1}$ and a new edge connecting $f^{\prime}_{2}$ to $f_{j}$. There
is now a path of even length between $f_{i}$ and $f_{j}$ that enforces the
same edge condition that we had before. Let the correspondingly changed graph
be $G^{\prime\prime}$. It can be verified that $G^{\prime\prime}$ is
bipartite.