# Graph multicoloring reduction methods and application to McDiarmid-Reed’s
Conjecture

Jean-Christophe Godin a Olivier Togni b

###### Abstract

A $(a,b)$-coloring of a graph $G$ associates to each vertex a set of $b$
colors from a set of $a$ colors in such a way that the color-sets of adjacent
vertices are disjoint. We define general reduction tools for $(a,b)$-coloring
of graphs for $2\leq a/b\leq 3$. In particular, we prove necessary and
sufficient conditions for the existence of a $(a,b)$-coloring of a path with
prescribed color-sets on its end-vertices. Other more complex
$(a,b)$-colorability reductions are presented. The utility of these tools is
exemplified on finite triangle-free induced subgraphs of the triangular
lattice. Computations on millions of such graphs generated randomly show that
our tools allow to find (in linear time) a $(9,4)$-coloring for each of them.
Although there remain few graphs for which our tools are not sufficient for
finding a $(9,4)$-coloring, we believe that pursuing our method can lead to a
solution of the conjecture of McDiarmid-Reed.

a Institut de Mathématiques de Toulon, Université de Toulon, France

<EMAIL_ADDRESS>
b Laboratoire LIB, Université Bourgogne Franche-Comté, France

<EMAIL_ADDRESS>
##  1 Introduction

For two integers $a$ and $b$, a $(a,b)$-coloring of a graph $G$ is a mapping
which associates to each vertex a set of $b$ colors from a set of $a$ colors
in such a way that adjacent vertices get disjoints sets of colors. In
particular, a $(a,1)$-coloring is simply a proper coloring. Equivalently, a
$(a,b)$-coloring of $G$ is a homomorphism to the Kneser graph $K_{a,b}$. This
type of coloring is also in relation with fractional colorings: the fractional
chromatic number of a graph $G$ can be defined as
$\chi_{f}(G)=\min\\{a/b,G\text{ is }(a,b)\text{colorable}\\}$.

Since the introductory paper of Stahl [11], multicoloring attracted a lot of
research, one of the most recent result being the one of Cranston and Rabern
[2] showing that planar graphs are $(9,2)$-colorable.

An associated problem is weighted coloring in which the number of colors to
assign can vary from vertex to vertex. Weighted coloring has a natural
application for frequency allocation in cellular networks [5]. In particular,
since the equidistant placement of transmitters induces a triangular lattice,
weighted coloring of triangular lattices has been the subject of many studies
[5, 6, 7, 9]. In most of these works the aim is to bound the weighted
chromatic number by a constant times the weighted clique number. Multicoloring
is a particular case of weighted coloring, however the fact that a graph is
$(a,b)$-colorable can be translated into a bound for weighted chromatic number
in terms of weighted clique, see [13] for instance.

Any graph with at least one edge is not $(a,b)$-colorable for $a<2b$, so it is
useful to introduce $e=a-2b$, $e$ symbolizing the entropy of the
$(a,b)$-coloring. Also, a graph is $(2b,b)$-colorable if and only if it is
bipartite. In this paper we concentrate on the pairs $(a,b)$ such that
$2<\frac{a}{b}\leq 3$, thus $e\in\\{1,...,b\\}$. It is easy to observe that if
a graph is $(a,b)$-colorable then it is also $(am,bm)$-colorable for any
$m\geq 1$. Moreover, the following decomposition property also holds: for any
integer $y\geq 1$, if $G$ is $(2x+1,x)$-colorable for any
$x\in\\{1,\ldots,y\\}$, then $G$ is $(a,b)$-colorable for any $a,b$ such that
$\frac{a}{b}\geq\frac{2y+1}{y}$. Hence $(2b+1,b)$-colorings are the extremal
objectives for non-bipartite graphs.

For finite triangle-free induced subgraphs of the triangular lattice, called
hexagonal graphs in this paper, it is easy to observe that they are
$(3,1)$-colorable and it has been proven by Havet [4] that such graphs are
also $(5,2)$-colorable and $(7,3)$-colorable. Sudeep and Vishwanathan [12]
then presented a simpler $(14,6)$-coloring algorithm and later, Sau et al. [8]
a simpler $(7,3)$-coloring, but using the four colors theorem as a subroutine.
The list version has been considered by Aubry et al. [1]. They showed that
hexagonal graphs are $(5m,2m)$-choosable. Of course, as a hexagonal graph can
have an induced 9-cycle, the best we can hope is to find a $(9,4)$-coloring.
In 1999, McDiarmid and Reed proposed the following conjecture (initially
stated in terms of weighted coloring):

######  Conjecture 1 (McDiarmid-Reed [6]).

Every hexagonal graph is $(9,4)$-colorable.

The aim of this paper is to define general reducible configurations for
$(a,b)$-coloring when $2<a/b\leq 3$, that may allow to prove that some graphs
are $(a,b)$-colorable. In particular, we will apply our reduction tools on
triangle-free induced subgraphs of the triangular lattice, in order to solve
Conjecture 1. The results are based on the Ph.D. thesis of Godin [3] that
contains also reducibility results for $(a,b)$-choosability, even when
$a/b\geq 3$. Searching for reducible configurations is common when dealing
with graph (multi)coloring. It is for instance a part of the discharging
method, a method extensively used for proving colorability properties on
planar or bounded maximum average degree graphs. In the case $2<a/b\leq 3$,
reducible configurations for $(a,b)$-coloring take the form of induced paths
in which interior vertices have degree 2 in the graph, called handles. In
order to get sharper results, we have also to define more sophisticated
handles by looking at the lengths of the induced paths that start at one or
both of the end-vertices of the handle (in which cases we speak about S-handle
and H-handle, respectively).

The paper is organized as follows: in Section 2 we define the different types
of handles we will consider and present the general handle-reducibility
results. As the associated proofs are technical and quite long, we postpone
them to the last sections of the paper. In Section 3 we apply our reduction
tools on finite triangle-free induced subgraphs of the triangular lattice, in
order to try to solve Conjecture 1. We also present the results of our
computations that give empirical evidence toward the conjecture and list some
possible extensions of this work and a conjecture generalizing Conjecture 1.
In Section 4, the necessary and sufficient conditions under which a path is
$(a,b)$-colorable when its end-vertices are already precolored are determined.
These results constitute the basic tools that we will use to prove the results
presented in Section 2. Section 5 is devoted to finding special
$(2b+1,b)$-colorings of a path in order to prove handle-reducibility in the
next section. In Section 6, we prove the reducibility results for S-handles
and H-handles.

##  2 Handle reductions

The path $P^{n}$ of length $n$ is the graph with vertex set $\\{0,\ldots,n\\}$
and edge set $\\{i(i+1),i=0,1,\ldots,n-1\\}$.

A handle $P(n)$ of length $n$ in a graph $G$ is a path of length $n$ that is
an induced subgraph of $G$ with vertices of degree two in $P(n)$ having the
same degree in $G$. The interior $\mathsf{int}(H)$ of a handle $H$ is the set
of vertices of degree 2 of $H$.

A parity handle (or P-handle) $PP(n)$ in a graph $G$ is a handle $P(n)$ with
the additional property that there exists another path of length $m\leq n$, of
the same parity than $n$ in $G-\mathsf{int}(P(n))$, between the two end-
vertices of $P(n)$.

An S-handle $S(n_{1},n_{2},n_{3})$ in a graph $G$ is a handle of length
$n_{1}$ such that one of its end-vertices has degree 3 in $G$ and is also the
end-vertex of two other handles of length $n_{2}$ and $n_{3}$.

An H-handle $H(n_{1},n_{2},n,n_{3},n_{4})$ in a graph $G$ is a handle of
length $n$ such that its two end-vertices are of degree three in $G$ and one
of them is also the end-vertex of two other handles of length $n_{1}$ and
$n_{2}$ and the other end-vertex is also the end-vertex of two handles of
length $n_{3}$ and $n_{4}$. Examples of handles are illustrated in Figure 1.

For a handle $H=S(n_{1},n_{2},n_{3})$, the two distinct end-vertices of the
paths of length $n_{2},n_{3}$ of $H$ are called the ports of $H$ and similarly
for $H=H(n_{1},n_{2},n,n_{3},n_{4})$, the four distinct end-vertices of the
paths of length $n_{1},n_{2},n,n_{3},n_{4}$ of $H$ are called its ports. Due
to symmetry reasons, we will consider only S-handles with $n_{1}\geq n_{2}\geq
n_{3}$ and H-handles with $n_{1}\leq n_{2}\leq n$ and $n_{4}\leq n_{3}\leq n$.
Note that (some of) the ports of a handle may be the same vertices (hence a
handle may induce a cycle in the graph).

$P(5)$$PP(4)$$S(4,3,2)$$H(1,2,5,3,2)$ Figure 1: Examples of handles in a
graph, from left to right: handle, parity handle, S-handle and H-handle (
white vertices: end-vertices of the handle).

A handle $H$ is $(a,b)$-reducible in a graph $G$ if any $(a,b)$-coloring of
$G-\mathsf{int}(H)$ can be extended to a $(a,b)$-coloring of $G$, possibly,
for S- and H-handles, by modifying the color sets of some vertices of degree 2
of $H$.

For a graph $G$ and a family $\mathcal{F}$ of handles in $G$, we define
$\mathsf{core}_{\mathcal{F}}(G)$ as any (induced) subgraph obtained after
successively removing vertices of degree 0 and 1 and vertices of
$\mathsf{int}(H)$ for each handle $H\in\mathcal{F}$ until no more degree 0 or
1 vertex nor handle of $\mathcal{F}$ remains. By the definition of
reducibility, we immediately have the following result:

######  Theorem 2.

For any graph $G$ and any family $\mathcal{F}$ of $(a,b)$-reducible handles in
$G$,

$G\ (a,b)\text{-colorable}\Leftrightarrow\mathsf{core}_{\mathcal{F}}(G)\
(a,b)\text{-colorable.}$

For any real $x$, let $\mathsf{Even}(x)$ be the minimum even integer $m$ such
that $m\geq x$. We will prove the following reducibility results in the next
Sections.

######  Theorem 3.

For any graph $G$ and any integers $b,e$ such that $b\geq 2$ and $e<b$, any
handle $P(n)$ with $n\geq\mathsf{Even}(2b/e)$ is $(2b+e,b)$-reducible in $G$
and any parity handle $PP(n)$ with $n\geq 2$ is $(2b+e,b)$-reducible in $G$.

For two integer vectors
$\boldsymbol{v}=(v_{1},v_{2},\ldots,v_{k}),\boldsymbol{v^{\prime}}=(v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{k})$
of $\mathbb{N}^{k}$ we consider the natural order:
$\boldsymbol{v}\leq\boldsymbol{v^{\prime}}$ if and only if $\forall
i\in\\{1,\ldots,k\\}$, $v_{i}\leq v^{\prime}_{i}$. Therefore, we will say that
an S-handle $S(n_{1},n_{2},n_{3})$ is smaller than an S-handle
$S(n^{\prime}_{1},n^{\prime}_{2},n^{\prime}_{3})$ if
$(n^{\prime}_{1},n^{\prime}_{2},n^{\prime}_{3})>(n_{1},n_{2},n_{3})$ and
similarly for H-handles.

######  Theorem 4.

For any graph $G$ and any integers $b,e,k$ such that $b\geq\max\\{2,e+1,k\\}$,
$S(\mathsf{Even}(2b/e)-1,2,1)$ is a smallest $(2b+e,b)$-reducible S-handle and
$S(2b-k,k,k)$ is a smallest $(2b+1,b)$-reducible S-handle in $G$.

######  Theorem 5.

For any graph $G$ and any integers $b,e$ such that $b\geq 2$ and $e<b$,
$H(1,2,\mathsf{Even}(2b/e)-2,2,1)$ is a smallest $(2b+e,b)$-reducible H-handle
and the following H-handles are smallest $(2b+1,b)$-reducible H-handles in
$G$:

  * •

$H(2,2,2b-3,2,2)$, $H(1,2,2b-3,3,2)$, $H(1,4,2b-3,2,2)$;

  * •

$H(2,3,2b-4,3,2)$, $H(2,2,2b-4,4,2)$, $H(2,2,2b-4,3,3)$, $H(1,2,2b-4,4,3)$,
$H(1,4,2b-4,3,3)$.

Remark that we do not try to go below $2b-4$ for the third parameter of a
H-handle since these results will be mainly used for the case $(a,b)=(9,4)$ in
Section 3, and for these values we have $2b-4=4$. Hence going below 4 will
result in a H-handle with $n\leq n_{3}$ (i.e., the handle is not ’centered’ on
the longest path). Nevertheless, similar results can be obtained for lower
values of $n$ (and greater values of $b$).

It can be shown (but the proof is tedious) that for the above handles, the
core is in fact unique, i.e., whatever the order of the reductions made, the
process will end with the same graph.

######  Theorem 6 (Unicity of the core).

For any graph $G$ and the family $\mathcal{F}$ of all handles from Theorems 3,
4, 5 for fixed $b\geq 2$ and $e<b$ in $G$, $\mathsf{core}_{\mathcal{F}}(G)$ is
unique.

The idea is to prove that if at some step of reducing the graph in order to
obtain a core we have the choice of reducing at least two handles, then the
order in which we do these reductions will not change the obtained core at the
end. For instance, suppose that $b=3,e=1$, and $G$ is a graph with two
reducible handles $H$ and $H^{\prime}$. Then either $H$ and $H^{\prime}$ are
disjoint and hence the order in which we reduce them has no importance, or
they share a common end-point. Suppose that $H$ is a handle $P(6)$ with end-
vertices $x$ and $y$ and that the end-vertices of $H^{\prime}$ are $y$ and $z$
and that the other induced path starting from $y$ in $G$ is of length
$\ell\geq 1$. Then if $H^{\prime}$ is reduced before $H$, the length of $H$
will increase to $6+\ell$ and it will thus remain reducible by Theorem 3. The
idea is similar if $H$ is an S-handle or H-handle. For example, let us now
suppose that $H$ is handle $H(1,4,2b-4,3,3)$ and $b\geq 4,e=1$. Then,
depending on the subpath of $H$ that is removed by removing the interior of
$H^{\prime}$, there will remain a handle $P(2b)$ or $S(2b-3,3,3)$ or
$S(2b-1,4,1)$, each being reducible in $G$.

##  3 Multicoloring triangle-free induced subgraphs of the triangular lattice

A finite triangle-free induced subgraph of the triangular grid will be called
a hexagonal graph.

In a similar way than the method used by Havet [4], i.e., starting from a
degree 3 vertex in a ’corner’ of the graph and exploring the configurations
around it for proving that a handle from $\mathcal{F}$ is present, we can
prove the following:

######  Theorem 7.

Let $G$ be a hexagonal graph. For each of the following three families of
handles we have $\mathsf{core}_{\mathcal{F}}(G)=\emptyset$:

  1. 1.

$\mathcal{F}=\\{P(2)\\}$;

  2. 2.

$\mathcal{F}=\\{P(4),PP(3)\\}$;

  3. 3.

$\mathcal{F}=\\{P(6),PP(3),PP(4),PP(5),S(5,2,1),H(1,2,4,2,1)\\}$.

###### Proof.

(Sketch of) Let $G$ be a hexagonal graph.

Since $G$ is finite, it is easy to observe that $G$ contains a handle $P(2)$
and hence $\mathsf{core}_{\\{P(2)\\}}(G)=\emptyset$.

We now prove that $\mathsf{core}_{\\{P(4),PP(3)\\}}(G)=\emptyset$. Let us call
a vertex of degree 3 in $G$ a node. If $G$ has no nodes, then $G$ is a union
of cycles of length at least 6, hence it contains a handle $P(4)$. Now, assume
that $G$ has at least one node. As explained in [4, 1], $G$ can be embedded in
the plane in such a way that edges leaving each vertex are only in at most
three of the six following directions: left (L), right (R), up-left (UL), up-
right (UR), down-left (DL), down-right (DR). According to this, there are two
kinds of nodes: left nodes (with L-edge, UR-edge and DR-edge) and right nodes
with (R-, UL- and DL-edges). The idea is to look at a node $x$ the most on the
left among those the most on the top. We can assume w.l.o.g. that $x$ is a
left node (see [4, 1] for details). For a node $v$ and a direction $D$ among
L,R,UL,UR,DL,DR, let us call the $D$-path from $v$ the induced path ending on
a node $y$ and with vertices of degree two starting by the $D$-edge from $v$.
Consider the UR-path $P$ from $x$. If $P$ has length at least 4 then we are
done. Otherwise, since the first edge of $P$ is a UR-edge and $x$ is the node
the most on the top, the only remaining possibility is that of $P$ having
length 3. In this case, we have an induced hexagon and hence a parity handle
$PP(3)$ of length 3.

For the case $\mathcal{F}=\\{P(6),PP(3),PP(4),PP(5),S(5,2,1),H(1,2,4,2,1)\\}$,
we proceed similarly as for the previous case, with $x$, $y$ and $P$ being
defined accordingly and $y$ being the end-vertex of $P$ other than $x$. If $P$
has length at least 6 then we have a handle $P(6)$. Otherwise if $P$ has
length 5, then we have either a handle $S(5,2,1)$ if one of the neighbors of
$x$ or $y$ outside $P$ has degree two or a parity handle (there are seven
possible configurations, see [3]). If $P$ has length 4 then either we have a
handle $H(1,2,4,2,1)$ or the two neighbors of $y$ outside $P$ are also nodes
and we have a parity handle $PP(4)$ (see Figure 2 for the three possible
configurations). If $P$ has length 3, as for the previous case, we have a
parity handle $PP(3)$. ∎

$x$$y$$x$$y$$x$$y$ Figure 2: Three types of parity handles $PP(4)$ between
nodes $x$ and $y$ in a hexagonal graph.

This theorem along with Theorems 3, 4, 5 allow to prove the known results [4]
for $(a,b)$-colorability of hexagonal graphs for $b=1,2$ and 3 in a unified
way:

######  Corollary 8.

Any hexagonal graph is $(3,1)$-colorable, $(5,2)$-colorable and
$(7,3)$-colorable.

For $a=9$ and $b=4$, the above results allow to prove simply the result of
Witkowski and Žerovnik [13], where a corner is a vertex of degree 2 or 3
adjacent to at least two vertices of non opposite directions:

######  Proposition 9.

Any hexagonal graph without adjacent corners is $(9,4)$-colorable.

###### Proof.

Let $G$ be a hexagonal graph without adjacent corners. We use the same
notation as for the proof of Theorem 7.

Assume that $G$ has at least one node. By Theorem 4, it suffices to prove that
$G$ contains an S-handle $S(6,2,2)$. Let $x$ be a node the most on the left
among those the most on the top. We assume w.l.o.g. that $x$ is a left node.
As $G$ has no adjacent corners (hence no adjacent nodes), the L-path and DR-
path from $x$ both have length at least 2. Now we show that the UR-path $P$
from $x$ has length at least 6. By the non-adjacent corner hypothesis, $P$
consists of at least two UR-edges, followed by at least two R-edges. Then,
since $x$ is the node the most on the top, we have to continue in $P$ with at
least two DR-edges in order to reach a node with an ordinate value equal to
the one of $x$. Consequently, the three paths emanating from $v$ together form
(at least) a handle $S(6,2,2)$. ∎

For any hexagonal graph $G$, consider the following set of handles:
$\mathcal{F}_{9,4}=\mathcal{P}\cup\mathcal{S}\cup\mathcal{H}$, with
$\mathcal{P}=\\{P(8),PP(3),PP(4),PP(5),PP(6),PP(7)\\}$,
$\mathcal{S}=\\{S(7,2,1),S(6,2,2),S(5,3,3),S(4,4,4)\\}$, and
$\mathcal{H}=\\{H(1,2,6,2,1),H(1,2,5,3,2),H(1,4,5,2,2),H(2,2,5,2,2),H(2,2,4,4,2),H(2,2,4,3,3)$,
$H(1,2,4,4,3),H(2,3,4,3,2),H(1,4,4,3,3)\\}$.

Note that, by Theorems 3, 4, 5, the handles of $\mathcal{F}_{9,4}$ are all
$(9,4)$-reducible. Moreover, all the handles of $\mathcal{F}_{9,4}$ are
necessary since we have examples of hexagonal graphs for which the core is not
empty if we remove one of the handles from $\mathcal{F}_{9,4}$. Figure 3 shows
three examples of hexagonal graphs that only possess handles from
$\mathcal{H}$ (the graph on the left contains only handles $H(2,4,4,4,2)$
(hence also $H(2,2,4,4,2)$), the one on the center only handles $H(1,2,6,2,1)$
and the one on the right only handles $H(2,2,4,4,2)$.

Figure 3: Three hexagonal graphs that only have $(9,4)$-reducible H-handles.

###  3.1 More $(9,4)$-reducible handles

In order to (try to) prove Conjecture 1, we found a set of thirteen (more
sophisticated) $(9,4)$-reducible configurations that we denote by
$\mathcal{F}^{\prime}_{9,4}$. The elements of $\mathcal{F}^{\prime}_{9,4}$ are
presented in Figure 4. These configurations are in fact H-handles with some
additional constraints (other paths of prescribed length between some ports).

######  Proposition 10.

For any graph $G$, every handle from $\mathcal{F}^{\prime}_{9,4}$ from Figure
4 is $(9,4)$-reducible in $G$.

###### Proof.

We only prove that the handle depicted on the top left of Figure 4 is
$(9,4)$-reducible. The result for the other configurations can be proved
similarly, whereas some configurations require a deeper (and tedious) case
analysis. They have all been tested by computer.

Let $G$ be a graph containing this configuration, i.e., a handle
$H=H(2,2,4,2,2)$ with the additional constraints $d_{G}(v_{1},v_{2})=2$ and
$d_{G}(v_{3},v_{4})=2$, where $h_{0}$ and $h_{4}$ are the end-vertices of the
handle and $v_{1}$, $v_{2}$ are the extremities of the paths of length 2 from
$h_{0}$ and $v_{3},v_{4}$ are the extremities of the paths of length 2 from
$h_{4}$, see Section 6. Let $\varphi$ be a $(9,4)$-coloring of
$G-\mathsf{int}(H)$. By the additional conditions, we have
$|\varphi(v_{1})\cap\varphi(v_{2})|\geq 3$ and
$|\varphi(v_{3})\cap\varphi(v_{4})|\geq 3$. Hence there exist $X$ and $Y$ such
that $|X\cap\varphi(v_{1})\cap\varphi(v_{2})|=3$ and
$|Y\cap\varphi(v_{3})\cap\varphi(v_{4})|=3$. If $|X\cap Y|<2$, then choose any
$x\in Y-X$ and any $y\in X-Y$ else choose any $x\in\\{1,\ldots,a\\}-X$ and any
$y\in\\{1,\ldots,a\\}-Y$. Then, we have
$|(X\cup\\{x\\})\cap(Y\cup\\{y\\})|\geq 2$, hence, by Theorem 19, the coloring
$\varphi$ can be extended to $G$ by setting $\varphi(h_{0})=X\cup\\{x\\}$ and
$\varphi(h_{4})=Y\cup\\{y\\}$. ∎

22242222224321222432322232223224222224321224231135433342142142243212522234243435111621
Figure 4:  $\mathcal{F}^{\prime}_{9,4}$: a new set of $(9,4)$-reducible
H-handles (numbers: path lengths; plain lines: induced paths with degree 2
interior vertices; dashed lines: induced paths with possibly vertices of
degree greater than two).

With these new reductions, we can state the following equivalent form of
Conjecture 1:

######  Conjecture 11.

For every hexagonal graph $G$,
$\mathsf{core}_{\mathcal{F}_{9,4}\cup\mathcal{F}^{\prime}_{9,4}}(G)$ is
$(9,4)$-colorable.

###  3.2 Computations

We have performed computational experiments for testing the reduction tools
defined in the previous section on hexagonal graphs for finding a
$(9,4)$-coloring. The algorithms were coded in C++ and ran on a Intel Xeon CPU
at $2.67$ GHz. The computations are grouped into two sets: in the first one,
$\mathsf{core}_{\mathcal{F}_{9,4}}$ is computed for randomly generated
hexagonal graphs while in the second one we compute
$\mathsf{core}_{\mathcal{F}_{9,4}\cup\mathcal{F}^{\prime}_{9,4}}$ on ’hard’
instances of hexagonal graphs containing many induced 9-cycles.

#### Experiment 1: basic reduction

Graph generation:  The graphs are generated randomly on a grid of size
$\ell\times h$ by choosing randomly the coordinates of a point and testing if
the corresponding vertex can be added to the graph without creating a triangle
(repeated $10\ell h$ times). In order to obtain the ’harder’ instances of
random hexagonal graphs, we then do a final pass in which we consider the
points of the grid in sequence and test if they can be added to the graph.
Hence the graphs obtained are maximal triangle-free subgraphs of the
triangular lattice, i.e., no point in the area can be added without creating a
triangle.

Reduction algorithm:  it consists in testing, for each vertex $x$ in sequence,
if $x$ is the end-vertex of a handle from $\mathcal{F}_{9,4}$.

Grid size $\ell\times\ell$ |  number of graphs tested |  mean density |  mean order |  H-ratio (per 1000) |  computation time (s) |  number of graphs with $\mathsf{core}_{\mathcal{F}_{9,4}}\neq\emptyset$
---|---|---|---|---|---|---
10 |  10000000 |  20 |  35 |  0 |  732 |  0
12 |  10000000 |  23 |  56 |  0.0006 |  1020 |  0
16 |  10000000 |  27 |  108 |  0.0016 |  2000 |  0
20 |  10000000 |  29 |  176 |  0.0062 |  3030 |  0
30 |  10000000 |  32 |  416 |  0.0335 |  7296 |  0
50 |  1000000 |  34 |  1193 |  0.184 |  22140 |  0
100 |  1000000 |  36 |  4868 |  1.118 |  9792 |  0
200 |  100000 |  36 |  19639 |  5.12 |  4278 |  0
500 |  20000 |  37 |  123345 |  36.65 |  6036 |  0
1000 |  1000 |  37 |  494129 |  142 |  1329 |  0
1500 |  1000 |  37 |  1112383 |  283 |  3243 |  0
Table 1: Summary of the computations on random hexagonal graphs.

The results are reported in Table 1 in which the first column indicates the
grid size, the second column reports the number of graphs generated and
tested, the third column indicates the mean density, i.e., the mean ratio of
degree-3 vertices, the fourth one indicates mean order of the graphs tested,
the fifth one reports the ratio of graphs that require at least a H-handle
reduction. Column 6 gives the time needed to test all the graphs and column 7
reports the number of graphs for which the core is not empty.

Our computations show that on thousand millions of graphs on grid sizes
ranging from $10\times 10$ to $1500\times 1500$, every graph has been reduced
completely, i.e., its core is empty. Moreover, the ratio of hexagonal graphs
that cannot be reduced completely without using H-handles is quite small
(although this ratio grows with the order of the graph, see column 5 of Table
1). However, as our intuition tells us that hexagonal graphs with many
9-cycles will be harder to reduce, we find a way to generate semi-random
hexagonal graphs with many 9-cycles by using the flower graph depicted on the
left of Figure 3, as explained in the following experiment.

#### Experiment 2: extended reduction

Graph generation $G_{p,d}$:  the grid size is fixed to $50\times 50$ and the
graphs are generated by first putting $p$ flower graphs isomorphic to the
graph depicted on the left of Figure 3, centered on the nodes of a regular
$p$-gon of side $d$ and then by completing randomly in order to obtain a
maximal induced triangle-free subgraph of the triangular grid, as described in
Experiment 1. For instance $G_{4,12}$ is a graph obtain by putting 4 flowers
at positions $(10,10),(10,22),(22,10),(22,22)$.

Reduction algorithm: it consists in testing, for each vertex $x$ in sequence,
if $x$ is the end-vertex of a handle from $\mathcal{F}_{9,4}$ or
$\mathcal{F}^{\prime}_{9,4}$.

distance $d$ | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
---|---|---|---|---|---|---|---|---|---|---|---
$\mathcal{F}_{9,4}$ | 100 | 100 | 0,08 | 0,59 | 0,31 | 0,18 | 0,089 | 0,04 | 0,025 | 0,012 | 0,004
$\mathcal{F}_{9,4}\cup\mathcal{F}^{\prime}_{9,4}$ | 100 | 100 | 0 | 0,14 | 0,013 | 0,013 | 0,002 | 0,003 | 0,002 | 0,002 | 0
Table 2: Percentage of irreducible configurations of graphs $G_{4,d}$
depending on the distance $d$ between flowers.

Experiments have been conducted with these new reducible configurations These
computations show that a very large proportion of the graphs $G_{p,d}$ can be
reduced completely with handles from
$\mathcal{F}_{9,4}\cup\mathcal{F}^{\prime}_{9,4}$. However there remain some
configurations that are not reducible with these handles. Table 2 presents the
percentage of graphs $G_{4,d}$ for which the core is not empty, depending on
the distance $d$ between flowers and Figure 5 presents two such examples.
Notice that for distance $d=8$ or 9, no graph is reducible since the graph on
the right side of Figure 5 is always present.

Figure 5: Two hexagonal graphs that do not contain any handle from
$\mathcal{F}_{9,4}\cup\mathcal{F}^{\prime}_{9,4}$.

###  3.3 Possible Extensions

Even if we were not able to completely solve Conjecture 1, we believe it is
possible to find new $(9,4)$-reducible configurations in hexagonal graphs that
can lead to a proof of the conjecture in a similar way as for proving such
graphs are $(7,3)$-colorable, i.e., showing that in any hexagonal graph, there
always exists one of these $(9,4)$-reducible configurations somewhere in the
periphery of the graph. Such extended configuration can take the form of a a
H-handle with paths on each of its four extremities. The help of a computer
then become precious since the number of cases to consider to prove
reducibility will increase.

Another possible direction is to restrict to subclasses of hexagonal graphs,
for instance we can ask: is any hexagonal graph with odd-girth 11
$(9,4)$-colorable? or even $(11,5)$-colorable? We thus propose the following
conjecture that generalizes Conjecture 1:

######  Conjecture 12.

For any $k\geq 1$, any hexagonal graph $G$ of odd-girth at least $2k+1$ is
$(2k+1,k)$-colorable.

The conjecture is true for $k\leq 3$ and for $k=4$ for hexagonal graphs $G$
such that
$\mathsf{core}_{\mathcal{F}_{9,4}\cup\mathcal{F}^{\prime}_{9,4}}(G)=\emptyset$
and more generally for hexagonal graphs $G$ such that there exists a family
$\mathcal{F}$ for which $\mathsf{core}_{\mathcal{F}}(G)=\emptyset$.

The three-dimensional generalization (called cannonball graph [10]) seems also
interesting. One question could be: is it true that any triangle-free subgraph
of the 3D triangular grid is $(5,2)$-colorable?

##  4 Path multicoloring

In this section we present general results about $(a,b)$-colorings of a path
with precolored end-vertices. As a corollary, we will obtain Theorem 3.

Recall that $a,b,e$ are three integers such that $a=2b+e$. We say that $X$ is
a good set if $|X|=b$ and $X\subset\\{1,...,a\\}$.

######  Definition 13.

Let $X,Y$ be good sets and $k$ be an integer. The sets $X$ and $Y$ are said to
be $k$-compatible if :

$|X\cap Y|\geq b-e\frac{k}{2}\ ,\ if\ k\ is\ even;$ $|X\cap Y|\leq
e\frac{k-1}{2}\ ,\ if\ k\ is\ odd.$

Moreover, if the above two inequalities are equalities, we say that $X$ and
$Y$ are $k$-exactly-compatible.

The following result is already proven in [5, Lemma 4] in a different way.

######  Theorem 14.

For any integer $n\geq 0$, if $\varphi$ is a $(a,b)$-coloring of the path
$P^{n}$, then $\varphi(0)$ and $\varphi(n)$ are $n$-compatible.

###### Proof.

Let $\varphi$ be a $(a,b)$-coloring of the path $P^{n}$. The assertion
trivially holds for $n=0$. If $n=1$ then since $v_{0}$ and $v_{1}$ are
neighbors, we have $\varphi(0)\cap\varphi(1)=\emptyset$ then
$|\varphi(0)\cap\varphi(1)|=0\leq 0$. If $n=2$ then we have
$\varphi(0)\cap\varphi(1)=\varphi(1)\cap\varphi(2)=\emptyset$, so
$b+e=a-b=|\\{1,...,a\\}\setminus\varphi(1)|\geq|\varphi(0)\cup\varphi(2)|=2b-|\varphi(0)\cap\varphi(2)|$,
then $|\varphi(0)\cap\varphi(2)|\geq b-e$.

Assume that the property is true for $n\geq 2$ even. Let $\varphi$ be a
$(a,b)$-coloring of $P^{n+2}$, then $\varphi(0)$ and $\varphi(n)$ are
$n$-compatible, i.e. $|\varphi(0)\cap\varphi(n)|\geq b-e\frac{n}{2}$ and
$\varphi(n)$ and $\varphi(n+2)$ are $2$-compatible, i.e.,
$|\varphi(n)\cap\varphi(n+2)|\geq b-e$. So
$|\varphi(0)\cap\varphi(n+2)|\geq|\varphi(0)\cap\varphi(n)\cap\varphi(n+2)|\geq|\varphi(0)\cap\varphi(n)|-|(\varphi(0)\cap\varphi(n))\setminus\varphi(n+2)|\geq(b-e\frac{n}{2})-e=b-e\frac{n+2}{2}$.

Assume now that the property is true for $n\geq 1$ odd. Let $\varphi$ be a
$(a,b)$-coloring of $P^{n+2}$, then since $\varphi(0)$, $\varphi(n)$ are
$n$-compatible and $\varphi(n)$, $\varphi(n+2)$ are $2$-compatible, we have
$|\varphi(0)\cap\varphi(n)|\leq e\frac{n-1}{2}$, and
$|\varphi(n)\cap\varphi(n+2)|\geq b-e$. So
$|\varphi(0)\cap\varphi(n+2)|=|\varphi(0)\cap\varphi(n)\cap\varphi(n+2)|+|(\varphi(0)\cap\varphi(n+2))\setminus\varphi(n)|\leq|\varphi(0)\cap\varphi(n)|+|\varphi(n+2)\setminus\varphi(n)|\leq
e\frac{n-1}{2}+e\leq e\frac{(n+2)-1}{2}$. ∎

For any two good sets $C_{0},C_{n}$, we define the canonical decomposition of
subsets:

$C(1)=C_{0}\cap C_{n}\ ,\ C(2)=C_{0}-C_{n}\ ,\ C(3)=C_{n}-C_{0}\ ,\
C(4)=\\{1,...,a\\}-C_{0}-C_{n}.$

For an $(a,b)$-coloring $\varphi$ of the path $P^{n}$, we define $\forall
j\in\\{1,2,3,4\\}$ and $\forall k\in\\{0,...,n\\}$ :

$c(j,k)=|\varphi(k)\cap C(j)|,$
$c(k)=\big{(}c(1,k),c(2,k),c(3,k),c(4,k)\big{)}.$

Therefore $\forall j\in\\{1,2,3,4\\}$ and $\forall k\in\\{0,...,n-1\\}$, we
have the property:

$c(j,k)+c(j,k+1)\leq|C(j)|.$

######  Proposition 15.

If $\varphi$ is a $(a,b)$-coloring of the path $P^{n}$ such that $n=2m$ is an
even integer and $b\geq em$ and $\varphi(0)$ and $\varphi(n)$ are $n$-exactly-
compatible, then $\forall k\in\\{0,...,n\\}$:

$c(k)=\left\\{\begin{array}[]{ll}(b-em,e(m-s),es,0),&\text{if }k=2s\text{ is
even};\\\ (0,es,e(m-s-1),b-e(m-1)),&\text{if }k=2s+1\text{ is
odd.}\end{array}\right.$

###### Proof.

Let $n=2m$ be an even integer such that $b\geq em$ and let $C_{0},C_{n}$ be
two $n$-exactly-compatible good sets. Then we have by construction
$|C(1)|=b-em$, $|C(2)|=|C(3)|=em$, and
$|C(4)|=a-|C(1)|-|C(2)|-|C(3)|=b-e(m-1)$.

If $\varphi$ is a $(a,b)$-coloring of the path $P^{n}$ such that
$\varphi(0)=C_{0}$ and $\varphi(n)=C_{n}$, then $\forall k\in\\{0,...,n\\}$:

  * •

If $k=2s$ is even, then by Theorem 14, $\varphi(k)$ and $\varphi(n)$ are
$(n-k)$-compatible and thus $|\varphi(k)\cap\varphi(n)|\geq
b-e\frac{n-k}{2}=b-e(m-s)$; $\varphi(k)$ and $\varphi(0)$ are $k$-compatible
and thus $|\varphi(k)\cap\varphi(0)|\geq b-e\frac{k}{2}=b-es$. So
$|\varphi(k)\setminus\varphi(0)|\leq es$ and thus $c(3,k)\leq es$. Since
$|C(1)|=b-em$ and $|\varphi(k)\cap\varphi(n)|\geq b-e(m-s)$ then $c(3,k)\geq
es$, so $c(3,k)=es$. Since $c(1,k)+c(2,k)=|\varphi(k)\cap\varphi(0)|\geq
b-es$, and $c(1,k)+c(2,k)+c(3,k)+c(4,k)=b$, then $c(4,k)=0$ and
$c(1,k)+c(2,k)=b-es$. Since $c(1,k)+c(3,k)=|\varphi(k)\cap\varphi(n)|\geq
b-e(m-s)$, we have $c(1,k)\geq b-em=|C(1)|$, and thus $c(1,k)=b-em$ and
$c(2,k)=e(m-s)$.

  * •

If $k=2s+1$ is odd, by the above, we have $c(2s)=(b-em,e(m-s),es,0)$ and
$c(2s+2)=(b-em,e(m-s-1),e(s+1),0)$. Since $|C(1)|=b-em=c(1,2s)$ then
$c(1,k)=0$. Since $|C(2)|=em$ and $c(2,2s)=e(m-s)$ then $c(2,k)\leq es$. Since
$|C(3)|=em$ and $c(3,2s+2)=e(s+1)$ then $c(3,k)\leq e(m-s-1)$. Since
$|C(4)|=b-e(m-1)$ then $c(4,k)\leq b-e(m-1)$. But
$c(1,k)+c(2,k)+c(3,k)+c(4,k)=b$, therefore all the inequalities are
equalities.

∎

######  Proposition 16.

If $\varphi$ is a $(2b+1,b)$-coloring of the path $P^{n}$ such that $n=2m+1$
is an odd integer and $b\geq em$ and $\varphi(0)$ and $\varphi(n)$ are
$n$-exactly-compatible, then $\forall k\in\\{0,...,n\\}$:

$c(k)=\left\\{\begin{array}[]{lllll}(e(m-s),&b-em,&0,&es),&\text{if
}k=2s\text{ is even};\\\ (es,&0,&b-em,&e(m-s)),&\text{if }k=2s+1\text{ is
odd.}\end{array}\right.$

###### Proof.

Let $n=2m+1$ be an odd integer such that $b\geq em$ and let $C_{0},C_{n}$ be
two $n$-exactly-compatible good sets. Then we have by construction
$|C(1)|=em$, since $|C_{0}|=|C_{n}|=b$ then $|C(2)|=|C(3)|=b-em$ , since
$|C(1)|+|C(2)|+|C(3)|+|C(4)|=a$ then $|C(4)|=e(m+1)$.

  * •

If $\varphi$ is a $(a,b)$-coloring of the path $P^{n}$ such that
$\varphi(0)=C_{0}$ and $\varphi(n)=C_{n}$, then $\forall k\in\\{0,...,n\\}$ :
If $k=2s$ is even, then by Theorem 14, then $\varphi(k)$ and $\varphi(n)$ are
$(n-k)$-compatible and thus $|\varphi(k)\cap\varphi(n)|\leq
e\frac{n-k-1}{2}=e(m-s)$; $\varphi(k)$ and $\varphi(0)$ are $k$-compatible and
thus $|\varphi(k)\cap\varphi(0)|\geq b-e\frac{k}{2}=b-es$. We have
$c(1,k)=|\varphi(0)\cap\varphi(k)|-c(2,k)\geq b-es-|\varphi(2)|=e(m-s)$. Since
$|\varphi(k)\cap\varphi(n)|\leq e(m-s)$ we have $c(1,k)\leq e(m-s)$, then
$c(1,k)=e(m-s)$. Therefore $c(2,k)=b-em$ and $c(3,k)=0$. Since
$c(1,k)+c(2,k)+c(3,k)+c(4,k)=b$, then $c(4,k)=es$.

  * •

If $k=2s+1$ is odd, by the above properties, we have
$c(2s)=(e(m-s),b-em,0,es)$ and $c(2s+2)=(e(m-s-1),b-em,0,e(s+1))$. Since
$|C(2)|=b-em$, then $c(2,k)=0$. Since $|C(1)|=em$, then $c(1,k)\leq es$. Since
$|C(4)|=e(m+1)$, then $c(4,k)\leq e(m-s)$. Since
$c(1,k)+c(2,k)+c(3,k)+c(4,k)=b$, then $c(3,k)\geq b-em=|C(3)|$, therefore all
the inequalities are equalities.

∎

In order to obtain a reciprocal result of Theorem 14, we define, for any
ordered set $I=\\{x_{1},\dots,x_{f}\\}$ (with $x_{1}<x_{2}\dots<x_{f}$),
$\mathsf{First}(k,I)=\\{x_{1},\dots,x_{k}\\}$, and
$\mathsf{Last}(k,I)=\\{x_{f-k+1},\dots,x_{f}\\}$. We have the following easy
useful fact:

$\mathsf{First}(k,I)\cap\mathsf{Last}(k^{\prime},I)=\emptyset\iff
k+k^{\prime}\leq|I|.$

######  Lemma 17.

If $C_{0},C_{n}$ are good sets such that $C_{0}$ and $C_{n}$ are $n$-exactly-
compatible, then a $(a,b)$-coloring $\varphi$ of the path $P^{n}$ such that
$\varphi(0)=C_{0}$ and $\varphi(n)=C_{n}$ can be computed in linear time.

###### Proof.

Let $C_{0},C_{n}$ be good $n$-exactly-compatible sets.

If $n=2m$ is even, then by Proposition 15, $\forall k\in\\{0,...,n\\}$ we set:

$\varphi(k)=\left\\{\begin{array}[]{ll}C(1)\cup\mathsf{First}(e(m-s),C(2))\cup\mathsf{First}(es,C(3))&\text{if
}\ k=2s\text{ is even};\\\
\mathsf{Last}(es,C(2))\cup\mathsf{Last}(e(m-s-1),C(3))\cup C(4)&\text{if
}k=2s+1\text{ is odd.}\end{array}\right.$

If $n=2m+1$ is odd, then by Proposition 16, $\forall k\in\\{0,...,n\\}$ we
set:

$\varphi(k)=\left\\{\begin{array}[]{ll}\mathsf{First}(e(m-s),C(1))\cup
C(2)\cup\mathsf{First}(es,C(4))&\text{if }\ k=2s\text{ is even};\\\
\mathsf{Last}(es,\varphi(1))\cup C(3)\cup\mathsf{Last}(e(m-s),C(4))&\text{if
}k=2s+1\text{ is odd.}\end{array}\right.$

Therefore we obtain in both cases in linear time a $(a,b)$-coloring $\varphi$
of $P^{n}$ such that $\varphi(0)=C_{0}$ and $\varphi(n)=C_{n}$. ∎

######  Lemma 18.

If $C_{0},C_{2n}$ are good sets such that $|C_{0}\cap C_{2n}|\geq b-e$, then a
$(a,b)$-coloring $\varphi$ of the path $P^{2n}$ such that $\varphi(0)=C_{0}$
and $\varphi(2n)=C_{2n}$ can be computed in linear time.

###### Proof.

Let $C_{0},C_{2n}$ be good sets such that $|C_{0}\cap C_{2n}|\geq b-e$, then
$|C_{0}\cup C_{2n}|\leq 2b-(b-e)=b+e$. Hence there exists a good set
$X\subset\\{1,...,a\\}-C_{0}-C_{2n}$. We set $\varphi(0)=C_{0}$, and $\forall
k\in\\{1,...,2n\\}$, $\varphi(k)=C_{2n}$ if $k$ is even, and $\varphi(k)=X$
otherwise. Therefore this linear time algorithm computes a $(2b+e,b)$-coloring
$\varphi$ of the path $P^{2n}$ such that $\varphi(0)=C_{0}$ and
$\varphi(2n)=C_{2n}$. ∎

These lemmas allow to prove the next result which is central in this paper as
it will be used several times in the next sections.

######  Theorem 19.

If $C_{0},C_{n}$ are $n$-compatible sets, then a $(a,b)$-coloring $\varphi$ of
the path $P^{n}$ such that $\varphi(0)=C_{0}$ and $\varphi(n)=C_{n}$ can be
computed in linear time.

###### Proof.

Let $C_{0},C_{n}$ be good $n$-compatible sets.

If $n$ is even, let $k=2s\in\\{0,...,n\\}$ be an even integer such that
$b-es\leq|C_{0}\cap C_{n}|<b-es+e$. Let $X\subset C_{0}\cap C_{n}$ such that
$|X|=b-es$ ; and $Y=C_{n}-C_{0}$, then $es\geq|Y|>es-e$. Let
$Z\subset\\{1,...,a\\}-C_{0}-C_{n}$ such that $|Z|=es-|Y|$. We choose
$C_{k}=X\cup Y\cup Z$, then $C_{k}$ is a good set and $|C_{0}\cap
C_{k}|=b-es$, therefore by Lemma 17, a $(a,b)$-coloring $\varphi$ of the path
$P^{k}$ such that $\varphi(0)=C_{0}$ and $\varphi(k)=C_{k}$ can be computed in
linear time. By construction $|C_{k}\cap C_{n}|>b-e$ and $n-k$ is even, then
by Lemma 18 we can complete the coloring for the rest of the path (between
$v_{k}$ and $v_{n}$) in linear time.

If $n$ is odd, let $k=2s+1\in\\{0,...,n\\}$ be an odd integer such that
$es\leq|C_{0}\cap C_{n}|<es+e$. Let $X\subset C_{0}\cap C_{n}$ such that
$|X|=es$; and $Y\subset C_{n}-C_{0}$ such that $|Y|=b-es-e$. Let
$Z\subset\\{1,...,a\\}-C_{0}-C_{n}$ such that $|Z|=e$. We choose $C_{k}=X\cup
Y\cup Z$, then $C_{k}$ is a good set and $|C_{0}\cap C_{k}|=es$, therefore by
Lemma 17, a $(a,b)$-coloring $\varphi$ of a path $P^{k}$ such that
$\varphi(0)=C_{0}$ and $\varphi(k)=C_{k}$ can be computed in linear time. By
construction $|C_{k}\cap C_{n}|=b-e$ and $n-k$ is even, then by Lemma 18 we
can complete the coloring for the rest of the path (between $v_{k}$ and
$v_{n}$) in linear time. ∎

If $C_{0},C_{n}$ are good sets such that $n\geq\mathsf{Even}(\frac{2b}{e})$,
then they are $n$-compatible and therefore we have the following result:

######  Corollary 20.

If $C_{0},C_{n}$ are good sets such that $n\geq\mathsf{Even}(\frac{2b}{e})$,
then a $(a,b)$-coloring $\varphi$ of the path $P^{n}$ such that
$\varphi(0)=C_{0}$ and $\varphi(n)=C_{n}$ can be computed in linear time.

######  Proposition 21.

If a graph $G$ contains a parity handle $H$ and $G-\mathsf{int}(H)$ is
$(a,b)$-colorable, then $G$ is $(a,b)$-colorable.

###### Proof.

Let $H=(v_{0},\ldots,v_{n})$ be a parity handle of length $n$ in $G$ such that
there exists a $(a,b)$-coloring $\varphi$ of $G-\mathsf{int}(H)$. Then, by
definition, there exists another path
$P^{\prime}=(v^{\prime}_{0}=v_{0},v^{\prime}_{1},\ldots,v^{\prime}_{n^{\prime}}=v_{n})$
in $G-\mathsf{int}(H)$ with $n\geq n^{\prime}$ and $n$ and $n^{\prime}$ having
the same parity. We extend the coloring $\varphi$ by setting $\forall
k\in\\{0,...,n^{\prime}\\},\varphi(v_{k})=\varphi(v^{\prime}_{k})$, and
$\forall k\in\\{n^{\prime}+1,...,n\\}$,
$\varphi(v_{k})=\varphi(v^{\prime}_{n^{\prime}})$ if $k-n^{\prime}$ is even
and $\varphi(v_{k})=\varphi(v^{\prime}_{n^{\prime}-1})$ otherwise. ∎

This proposition along with Corollary 20 allow to prove Theorem 3.

##  5 Algorithms for $(2b+1,b)$-coloring a path

This section contains a series of lemmas presenting properties on the color
sets of some interior vertices of a path with a given $(2b+1,b)$-coloring.
These lemmas will be used in Section 6.

Remember that the vertices of a path $P^{n}$ are denoted by
$v_{0},v_{1},\ldots,v_{n}$ and that for any two good sets $C_{0},C_{n}$,
$C(1)=C_{0}\cap C_{n}\ ,\ C(2)=C_{0}-C_{n}\ ,\ C(3)=C_{n}-C_{0}\ ,\
C(4)=\\{1,...,a\\}-C_{0}-C_{n}$.

######  Lemma 22.

For any $(2b+1,b)$-coloring $\varphi$ of $P^{4}$, there exist four distinct
good sets $X_{1}$, $X_{2}$, $X_{3}$ and $X_{4}$, such that

(i)

$|X_{1}\cap X_{2}|=|X_{1}\cap X_{3}|=b-1$, $|X_{1}\cap X_{4}|=b-2$, and

(ii)

for each $i\in\\{1,2,3,4\\}$, there exists a $(2b+1,b)$-coloring
$\varphi^{\prime}$ of $P^{4}$ such that
$\varphi^{\prime}(v_{0})=\varphi(v_{0})$,
$\varphi^{\prime}(v_{4})=\varphi(v_{4})$ and $\varphi^{\prime}(v_{2})=X_{i}$.

###### Proof.

Let $\varphi$ be a $(2b+1,b)$-coloring of $P^{4}$ and let
$C_{0}=\varphi(v_{0})$ and $C_{4}=\varphi(v_{4})$. By Theorem 14,
$|C(1)|=|C_{0}\cap C_{4}|\geq b-2$. Thus we have three cases to consider:

Case 1:

$|C(1)|=b$. We choose any $Y\subset C(1)$, any $Y_{1}\subset C_{0}-Y$,
$Y_{2}=C_{0}-Y-Y_{1}$, any $Z,Z^{\prime}\subset\\{1,...,a\\}-C_{0}$, such that
$|Y|=b-2$, and $|Z|=|Z^{\prime}|=|Y_{1}|=|Y_{2}|=1$. Then we set $X_{1}=Y\cup
Y_{1}\cup Z$, $X_{2}=C_{0}$, $X_{3}=Y\cup Y_{1}\cup Z^{\prime}$, and
$X_{4}=Y\cup Y_{2}\cup Z^{\prime}$.

Case 2:

$|C(1)|=b-1$. We choose any $Y\subset C(1)$, and any
$Z,Z^{\prime}\subset\\{1,...,a\\}-C_{0}-C_{4}$, such that $|Y|=b-2$, and
$|Z|=|Z^{\prime}|=1$, and we set $X_{1}=C(1)\cup Z$, $X_{2}=C_{0}$,
$X_{3}=C(1)\cup Z^{\prime}$ and $X_{4}=Y\cup(C_{0}-C(1))\cup(C_{4}-C(1))$.

Case 3:

$|C(1)|=b-2$. Then we note $C(2)=Y_{2}\cup Y^{\prime}_{2}$ and $C(3)=Y_{3}\cup
Y^{\prime}_{3}$, with $|Y_{i}|Y^{\prime}_{i}|=|=1$, for $i=1,2$, and we set
$X_{1}=D_{1}\cup Y_{2}\cup Y_{3}$, $X_{2}=C(1)\cup Y_{2}\cup Y^{\prime}_{3}$,
$X_{3}=C(1)\cup Y^{\prime}_{2}\cup Y_{3}$, and $X_{4}=C(1)\cup
Y^{\prime}_{2}\cup Y^{\prime}_{3}$.

For each case and each $i\in\\{1,2,3,4\\}$, the pairs $(C_{0},X_{i})$ and
$(X_{i},C_{4})$ are both $2$-compatible and thus Theorem 19 allows to
conclude. ∎

######  Lemma 23.

For any $(2b+1,b)$-coloring $\varphi$ of $P^{5}$, there exist two distinct
sets $X$ and $Y$ such that $|X|=|Y|=2$ and for any $x\in X$ and $y\in Y$ there
exists a $(2b+1,b)$-coloring $\varphi^{\prime}$ of $P^{5}$ such that
$\varphi^{\prime}(v_{0})=\varphi(v_{0})$,
$\varphi^{\prime}(v_{5})=\varphi(v_{5})$ and
$\\{x,y\\}\subset\varphi^{\prime}(v_{2})$.

###### Proof.

Let $\varphi$ be a $(2b+1,b)$-coloring of $P^{5}$ and let
$C_{0}=\varphi(v_{0})$ and $C_{5}=\varphi(v_{5})$. By Theorem 14, $|C(1)|\leq
2$ and thus $|C(2)|\geq b-2$.

Case 1:

$|C(1)|=0$. We choose any $I\subset C_{0}$, $X=C_{0}-I$ and any
$Y\subset\\{1,...,a\\}-C_{0}$, such that $|I|=b-2$, and $|Y|=2$.

Case 2:

$|C(1)|\geq 1$. We choose any $I\subset C(2)$, $X=C_{0}-I$ and $Y\subset C(4)$
such that $|I|=b-2$ and $|Y|=2$.

For each case and each $x\in X,y\in Y$, by construction,
$C_{0},I\cup\\{x,y\\}$ are 2-compatible and $I\cup\\{x,y\\},C_{5}$ are
3-compatible, hence Theorem 19 allows to conclude. ∎

######  Lemma 24.

For any $(2b+1,b)$-coloring $\varphi$ of $P^{2n+1}$ with $n\leq b-1$, there
exist two distinct sets $X$ and $Y$, such that $|X|=b-n$ and $|Y|=n+1$, and
for any $Y^{\prime}\subset Y$ such that $|Y^{\prime}|=n$, there exists a
$(2b+1,b)$-coloring $\varphi^{\prime}$ of $P^{2n+1}$ such that
$\varphi^{\prime}(v_{0})=\varphi(v_{0})$,
$\varphi^{\prime}(v_{2n+1})=\varphi(v_{2n+1})$ and
$\varphi^{\prime}(v_{1})=X\cup Y^{\prime}$.

###### Proof.

Let $n\leq b-1$ and $\varphi$ be a $(2b+1,b)$-coloring of $P^{2n+1}$ and let
$C_{0}=\varphi(v_{0})$ and $C_{2n+1}=\varphi(v_{2n+1})$. We have $|C(1)|\leq
n$ and thus $|C(3)|\geq b-n$. We choose any $X\subset C(3)$ with $|X|=b-n$ and
$Y=\\{1,...,a\\}-X-C_{0}$. For any $Y^{\prime}\subset Y$ such that
$|Y^{\prime}|=n$, we let $C_{1}=X\cup Y^{\prime}$. Then $|C_{0}\cap C_{1}|=0$
and $|C_{2n+1}\cap C_{1}|\geq b-n$, therefore Theorem 19 allows to conclude. ∎

######  Lemma 25.

For any $(2b+1,b)$-coloring $\varphi$ of $P^{4n}$ with $2n\leq b$, there
exists a set $X\subset\\{1,...,a\\}$ such that $|X|=b+2n$, and for any
$X^{\prime}\subset X$ with $|X^{\prime}|=n$, there exists a
$(2b+1,b)$-coloring $\varphi^{\prime}$ of $P^{4n}$ such that
$\varphi^{\prime}(v_{0})=\varphi(v_{0})$,
$\varphi^{\prime}(v_{4n})=\varphi(v_{4n})$ and
$X^{\prime}\subset\varphi^{\prime}(v_{2n})$.

###### Proof.

Let $2n\leq b$ and $\varphi$ be a $(2b+1,b)$-coloring of $P^{4n}$. Let
$C_{0}=\varphi(0)$ and $C_{4n}=\varphi(4n)$.

Case 1:

$|C(1)|\geq b-n$. We choose any set $X\subset\\{1,...,a\\}$ with $|X|=b+2n$,
and for any $X^{\prime}\subset X$ such that $|X^{\prime}|=n$, we choose any
$I\subset C(1)$ such that $|I|=b-n$, and we choose any $Y\subset C(4)$ such
that $|Y|=|I\cap X^{\prime}|$. We then set $C_{2n}=I\cup X^{\prime}\cup Y$.

Case 2:

$|C(1)|\leq b-n-1$. Let $i=b-n-|C(1)|$. We choose any set $X$ with $C_{0}\cup
C_{4n}\subset X\subset\\{1,...,a\\}$ and $|X|=b+2n$, and for any
$X^{\prime}\subset X$ such that $|X^{\prime}|=n$, we choose any $Y_{2}$ with
$X^{\prime}\cap C(2)\subset Y_{2}\subset C(2)$ and $|Y_{2}|=\max(i,|C(2)\cap
X^{\prime}|)$, and we choose any $Y_{3}$ with $X^{\prime}\cap C(3)\subset
Y_{3}\subset C(3)$ and $|Y_{3}|=\max(i,|C(3)\cap X^{\prime}|)$, and we choose
any $Z$ with $X^{\prime}\cap C(4)\subset Z\subset X-C(1)-Y_{2}-Y_{3}$ and
$|Z|=b-|C(1)|-|Y_{2}|-|Y_{3}|$. Such choice is always possible since
$|X^{\prime}\cap C(4)|\leq|X-C_{0}-C_{4n}|=b+2n-(b+n+i)=n-i$. We then set
$C_{2n}=C(1)\cup Y_{2}\cup Y_{3}\cup Z$.

In both cases, the pairs $(C_{0},C_{2n})$ and $(C_{2n},C_{4n})$ are both
$2n$-compatible and thus Theorem 19 allows to conclude. ∎

######  Lemma 26.

For any $(2b+1,b)$-coloring $\varphi$ of $P^{4n+2}$ with $3\leq 2n+1\leq b$,
there exists a set $X\subset\\{1,...,a\\}$ with $|X|=b+2n+1$, and for any
$X^{\prime}\subset X$ such that $|X^{\prime}|=n+1$, there exists a
$(2b+1,b)$-coloring $\varphi^{\prime}$ of $P^{4n+2}$ such that
$\varphi^{\prime}(v_{0})=\varphi(v_{0})$,
$\varphi^{\prime}(v_{4n+2})=\varphi(v_{4n+2})$ and
$X^{\prime}\cap\varphi^{\prime}(v_{2n+1})=\emptyset$.

###### Proof.

Let $\varphi$ be a $(2b+1,b)$-coloring of $P^{4n+2}$ and $3\leq 2n+1\leq b$.
Let $C_{0}=\varphi(v_{0})$ and $C_{4n+2}=\varphi(v_{4n+2})$.

Case 1:

$|C(1)|\geq b-n$. Let $i=b-|C(1)|$. We choose any set $X\subset\\{1,...,a\\}$
such that $|X|=b+2n+1$. For any $X^{\prime}\subset X$ such that
$|X^{\prime}|=n+1$, if $|C(4)-X^{\prime}|\geq b$ then we choose any good set
$I\subset C(4)-X^{\prime}$ and we set $C_{2n+1}=I$; otherwise we choose
$I=C(4)-X^{\prime}$, so $|I|=b-i+1-|X^{\prime}\cap C(4)|$. If $|I|\geq b-n$,
then we choose any $Y\subset C_{0}-X^{\prime}$ such that $|Y|=b-|I|$ and we
set $C_{2n+1}=I\cup Y$. Else ($|I|<b-n$), we let $Y_{2}=C(2)-X^{\prime}$. If
$|C(3)-X^{\prime}|\geq b-|I|-|Y_{2}|$, then we choose $Y_{3}\subset
C(3)-X^{\prime}$ such that $|Y_{3}|=b-|I|-|Y_{2}|$ and we set $C_{2n+1}=I\cup
Y_{2}\cup Y_{3}$. Otherwise, $|C(3)-X^{\prime}|<b-|I|-|Y_{2}|$, and then we
choose $Y_{3}=C(3)-X^{\prime}$. By construction we have
$|I|+|Y_{2}|+|Y_{3}|=|C(4)|+|C(2)|+|C(3)|-(n+1)+|X^{\prime}\cap C(1)|\geq
b+i-n$, then we choose any $Z\subset C(1)-X^{\prime}$ such that
$|Z|=b-|I|-|Y_{2}|-|Y_{3}|$ and we set $C_{2n+1}=I\cup Y_{2}\cup Y_{3}\cup Z$.

Case 2 :

$|C(1)|\leq b-n-1$. Let $i=b-n-|C(1)|$. We choose any set $C_{0}\cup
C_{4n}\subset X\subset\\{1,...,a\\}$ such that $|X|=b+2n+1$, and for any
$X^{\prime}\subset X$ such that $|X^{\prime}|=n+1$, we choose
$I=C(4)-X^{\prime}$. If $|C(2)-X^{\prime}|\geq n$, then we choose
$Y_{2}\subset C(2)-X^{\prime}$ such that $|Y_{2}|=n$. If
$|C(3)-X^{\prime}|\geq b-|I|-|Y_{2}|$ then we choose $Y_{3}\subset
C(3)-X^{\prime}$ such that $|Y_{3}|=b-|I|-|Y_{2}|$ and we set $C_{2n+1}=I\cup
Y_{2}\cup Y_{3}$. Otherwise, $|C(3)-X^{\prime}|<b-|I|-|Y_{2}|$, so
$b-n=|C(3)|+|C(4)|-|X^{\prime}|<b-|Y_{2}|=b-n$, a contradiction. We do the
same with $|C(3)-X^{\prime}|\geq n$. Else $|C(2)-X^{\prime}|<n$ and
$|C(3)-X^{\prime}|<n$, then we choose $Y_{2}=C(2)-X^{\prime}$. If
$|C(3)-X^{\prime}|\geq b-|I|-|Y_{2}|$, then we choose $Y_{3}\subset
C(3)-X^{\prime}$ such that $|Y_{3}|=b-|I|-|Y_{2}|$ and we set $C_{2n+1}=I\cup
Y_{2}\cup Y_{3}$. Otherwise, $|C(3)-X^{\prime}|<b-|I|-|Y_{2}|$, so $b+1\leq
b+|C(3)|-n=|C(3)|+|C(4)|+|C(2)|-|X^{\prime}|<b$, a contradiction.

Therefore by Theorem 19, the lemma is proved. ∎

##  6 S-handle and H-handle reductions

The purpose of this section is to prove Theorems 4 and 5 of Section 2. For an
S-handle $S(n,n_{1},n_{2})$, let $P=h_{0},h_{1},\cdots,h_{n}$ be the central
path and let $v_{1}$ and $v_{2}$ be the end-vertices of the paths of lengths
$n_{1}$ and $n_{2}$, respectively. Similarly, for a H-handle
$H(n_{1},n_{2},n,n_{3},n_{4})$, $P=h_{0},h_{1},\cdots,h_{n}$ is the central
path and $v_{1}$ and $v_{2}$, $v_{3}$ and $v_{4}$ are the end-vertices of the
paths of lengths $n_{1}$, $n_{2}$, $n_{3}$ and $n_{4}$, respectively. See
Figure 6 for an illustration.

$h_{0}$$h_{n}$$v_{1}$$v_{2}$$h_{0}$$h_{n}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$ Figure
6: notation for the vertices of S-handles (on the left) and H-handles (on the
right).

######  Proposition 27.

For any $b,e$ with $b\geq e$ and any graph $G$,
$S(\mathsf{Even}(\frac{2b}{e})-1,2,1)$ is a smallest $(2b+e,b)$-reducible
S-handle in $G$.

###### Proof.

Let $n=\mathsf{Even}(\frac{2b}{e})-1$.

For the minimality, we present a counter example showing that
$S(\mathsf{Even}(\frac{2b}{e})-1,1,1)$ is not reducible: if
$C(v_{1})=\\{1,\ldots,b\\}$, $C(v_{2})=\\{e+1,\ldots,b+e\\}$,
$C(h_{n})=\\{b+e+1,\ldots,2b+e\\}$, then the color set of $h_{0}$ must be
$\\{b+e+1,\ldots,2b+e\\}$ but then the color sets of $h_{0}$ and $h_{n}$ are
not $n$-compatible, hence a contradiction. Also, the handle
$S(\mathsf{Even}(\frac{2b}{e})-2,2,1)$ is not reducible since in this case
there is a path between $v_{2}$ and $h_{n}$ of length
$\frac{2b}{e}-2+1<\frac{2b}{e}$, hence the coloring cannot be extended to the
interior vertices of the handle if these two vertices have the same color set.

In order to prove reducibility, let $G$ be a graph containing a handle
$H=S(n,2,1)$ and $\varphi$ be a $(2b+e,b)$-coloring of $G-\mathsf{int}(H)$.
Let $X=\varphi(h_{n})$. We have $|\varphi(v_{1})\cap\varphi(v_{2})|\leq e$,
thus there exists $I\subset\varphi(v_{2})-\varphi(v_{1})$ such that $|I|=b-e$.
If $|X\cap(\\{1,...,a\\}-I-\varphi(v_{1}))|\leq e$, then there exists
$Y\subset\\{1,...,a\\}-I-\varphi(v_{1})-X$ such that $|Y|=e$. Otherwise,
$|X\cap(\\{1,...,a\\}-I-\varphi(v_{1}))|>e$, and there exists
$Y^{\prime}\subset(\\{1,...,a\\}-I-\varphi(v_{1}))\cap X$ such that
$|Y^{\prime}|=e-|\\{1,...,a\\}-I-\varphi(v_{1})-X|$. We then choose
$Y=(\\{1,...,a\\}-I-\varphi(v_{1})-X)\cup Y^{\prime}$. By construction,
$|X\cap(I\cup Y)|\leq b-e\leq e\frac{\mathsf{Even}(\frac{2b}{e})-2}{2}$, hence
by Theorem 19, there exists a $(2b+e,b)$-coloring $\varphi^{\prime}$ of $H$
such that $\varphi^{\prime}(v_{1})=\varphi(v_{1})$,
$\varphi^{\prime}(v_{2})=\varphi(v_{2})$, $\varphi^{\prime}(h_{n})=X$ and
$\varphi^{\prime}(h_{0})=I\cup Y$. ∎

######  Proposition 28.

For any graph $G$ and any integer $k$ with $2\leq k\leq b$, $S(2b-k,k,k)$ is a
smallest $(2b+1,b)$-reducible S-handle in $G$.

###### Proof.

Let $n=2b-k$.

The minimality follows from the fact that the handles $S(2b-k,k,k-1)$ and
$S(2b-k-1,k,k)$ are both not reducible since in both of them there is a path
of length $2b-1$ between $v_{2}$ and $h_{n}$, hence the color sets of these
two vertices must share at least $b-1$ common colors.

Let $G$ be a graph containing a handle $H=S(2b-k,k,k)$, with $k$ an integer
such that $2\leq k\leq b$, and let $\varphi$ be a $(2b+1,b)$-coloring of
$G-\mathsf{int}(H)$. Let $\varphi(v_{1})=C_{0}$ and $\varphi(v_{2})=C_{2k}$.
Then $C_{0},C_{2k}$ are $2k$-compatible. We are going to construct a good set
$C_{k}$ such that $C_{k},C_{0}$ and $C_{k},C_{2k}$ are both $k$-compatible and
$C_{k},\varphi(h_{n})$ are $(2b-k)$-compatible. Then, Theorem 19 will assert
that there exists a $(2b+1,b)$-coloring $\varphi^{\prime}$ of $H$, such that
$\varphi^{\prime}(h_{n})=\varphi(h_{n})$,
$\varphi^{\prime}(v_{1})=\varphi(v_{1})=C_{0}$ and
$\varphi^{\prime}(v_{2})=\varphi(v_{2})=C_{2k}$.

Case 1 :

$k=2m$ is even. By Lemma 25 there exists $X$ such that $|X|=b+2m$, then
$|X\cap\varphi(v_{n})|\geq b+2m+b-a=2m-1\geq m$, so there exists
$X^{\prime}\subset X\cap\varphi(h_{n})$ such that $|X^{\prime}|=m$ and
$X^{\prime}\subset C_{k}$. Therefore $|C_{k}\cap\varphi(h_{n})|\geq
m=b-\frac{2b-k}{2}$.

Case 2 :

$k=2m+1$ is odd. By Lemma 26 there exists $X$ such that $|X|=b+2m+1$, then
$|X\cap\varphi(h_{n})|\geq b+2m+1+b-a=2m\geq m+1$, so there exists
$X^{\prime}\subset X\cap\varphi(h_{n})$ such that $|X^{\prime}|=m+1$ and
$X^{\prime}\cap C_{k}=\emptyset$. Therefore $|C_{k}\cap\varphi(h_{n})|\leq
b-(m+1)=\frac{(2b-k)-1}{2}$.

∎

###  6.1 H-handle reductions

######  Proposition 29.

For any $b,e$ with $b\geq e$ and any graph $G$,
$H(1,2,\mathsf{Even}(\frac{2b}{e})-2,2,1)$ is a smallest $(2b+e,b)$-reducible
H-handle in $G$.

###### Proof.

Let $n=\mathsf{Even}(\frac{2b}{e})-2$.

For the minimality, it can be observed that $H(1,1,n,2,1)$ and
$H(1,2,n-1,2,1)$ are both not reducible since the first one is in fact an
S-handle $S(n,2,1)$ and is not reducible by Proposition 27 and the second one
has a path of length $1+n-1+1=n+1<\mathsf{Even}(\frac{2b}{e})$ between two of
its extremities and thus is not reducible.

Now let $G$ be a graph containing a handle $H=H(1,2,n,2,1)$ and let $\varphi$
be a $(2b+e,b)$-coloring of $G-\mathsf{int}(H)$. Let $v^{\prime}_{2}$ be the
common neighbor of $h_{0}$ and $v_{2}$ and $v^{\prime}_{3}$ be the common
neighbor of $h_{n}$ and $v_{3}$. By hypothesis,
$|\varphi(v_{1})\cap\varphi(v_{2})|\leq e$ and
$|\varphi(v_{3})\cap\varphi(v_{4})|\leq e$, hence
$|\varphi(v_{2})-\varphi(v_{1})|\geq b-e$ and
$|\varphi(v_{3})-\varphi(v_{4})|\geq b-e$. Let
$X\subset\varphi(v_{2})-\varphi(v_{1})$ and
$X^{\prime}\subset\varphi(v_{3})-\varphi(v_{4})$ such that
$|X|=|X^{\prime}|=b-e$. We are going to show that sets
$Y\subset\\{1,\ldots,a\\}-\varphi(v_{1})$ and
$Y^{\prime}\subset\\{1,\ldots,a\\}-\varphi(v_{4})$ can be chosen in such a way
that $C_{0}=X\cup Y$ and $C_{n}=X^{\prime}\cup Y^{\prime}$ are $n$-compatible,
i.e., $|C_{0}\cap C_{n}|\geq e$. Then, Theorem 19 will assert that there
exists a $(2b+e,b)$-coloring $\varphi^{\prime}$ of $H$, such that
$\varphi^{\prime}(h_{0})=C_{0}$, $\varphi^{\prime}(h_{n})=C_{n}$.

Let $L(h_{n})=\\{1,\ldots,a\\}-\varphi(v_{4})$ and
$L(h_{0})=\\{1,\ldots,a\\}-\varphi(v_{1})$. If $|X\cap X^{\prime}|\geq e$,
then $|C_{0}\cap C_{n}|\geq e$. Hence assume $|X\cap X^{\prime}|=z<e$. If
$|(L(h_{n})-X^{\prime})\cap X|\geq e-z$, then we choose $Y^{\prime}$ such that
$|Y^{\prime}\cap X|\geq e-z$, therefore $|C_{0}\cap C_{n}|\geq e$. Otherwise
$|(L(h_{n})-X^{\prime})\cap X|=t<e-z$. If $|(L(v_{0})-X)\cap X^{\prime}|\geq
e-z-t$, then we choose $Y$ such that $|Y\cap X^{\prime}|\geq e-z-t$, therefore
$|C_{0}\cap C_{n}|\geq e$. Otherwise $|(L(v_{0})-X)\cap
X^{\prime}|=t^{\prime}<e-z-t$. We note
$z^{\prime}=|(L(v_{0})-X)\cap(L(h_{n})-X^{\prime})|$. Since
$a\geq|L(v_{0})\cup L(h_{n})|=2b+2e-z-z^{\prime}-t-t^{\prime}$, we have
$z+z^{\prime}+t+t^{\prime}\geq e$. We choose
$Y_{0}\subset(L(v_{0})-X)\cap(L(h_{n})-X^{\prime})$ such that $|Y_{0}|=e-z-
t-t^{\prime}$. We choose $Y,Y^{\prime}$ such that
$Y_{0}\cup\big{(}(L(h_{n})-X^{\prime})\cap X\big{)}\subset Y^{\prime}$ and
$Y_{0}\cup\big{(}(L(v_{0})-X)\cap X^{\prime}\big{)}\subset Y$, therefore
$|C_{0}\cap C_{n}|\geq e$.

∎

In order to shorten some proofs for H-reducibility, we will use the two
following lemmas.

######  Lemma 30.

Let $n\geq 1$ and $G$ be a graph. If $H(n_{1},n_{2},n,n_{3},n_{4})$ is
$(a,b)$-reducible in $G$ and $H(n_{1},n_{2},n-1,n_{3}+1,n_{4}+1)$ is
$(a,b)$-reducible in $G$ when the color-sets of $v_{3},v_{4}$ are
$(n_{3}+n_{4}+2)$-exactly-compatible, then
$H(n_{1},n_{2},n-1,n_{3}+1,n_{4}+1)$ is $(a,b)$-reducible in $G$.

###### Proof.

Let $n\geq 1$. Let $H$ be a handle $H(n_{1},n_{2},n-1,n_{3}+1,n_{4}+1)$ in $G$
and $\varphi$ be a $(a,b)$-coloring of $G-\mathsf{int}(H)$. Assume
$H(n_{1},n_{2},n,n_{3},n_{4})$ is $(a,b)$-reducible in $G$, and
$H(n_{1},n_{2},n-1,n_{3}+1,n_{4}+1)$ is $(a,b)$-reducible in $G$ for
$\varphi(v_{3}),\varphi(v_{4})$ being $(n_{3}+n_{4}+2)$-exactly-compatible. If
$\varphi(v_{3}),\varphi(v_{4})$ are $(n_{3}+n_{4}+2)$-exactly-compatible then
it is true by hypothesis. Otherwise $\varphi(v_{3}),\varphi(v_{4})$ are
$(n_{3}+n_{4})$-compatible. Then, by hypothesis, there exists a
$(a,b)$-coloring $\varphi^{\prime}$ of
$H^{\prime}=H(n_{1},n_{2},n,n_{3},n_{4})$ with
$\varphi^{\prime}(v^{\prime}_{i})=\varphi(v_{i})$, where $v^{\prime}_{i}$ is
the end-vertex of the path of length $n_{i}$ of $H^{\prime}$, $i=1,\ldots,4$.
Now we complete the coloring of $G$: to each vertex of the paths of $H$ of
length $n_{1},n_{2}$, and $n-1$ starting at $h_{0}$ we associate the color of
the corresponding vertex in $H^{\prime}$; for the two neighbors of $h_{n-1}$
along the paths towards $v_{3}$ and $v_{4}$ we assign the color
$\varphi^{\prime}(h^{\prime}_{n})$; for the remaining subpaths of lengths
$n_{3}$ and $n_{4}$ of $H$, we use the colors of the corresponding paths of
the same lengths in $H^{\prime}$. We obtain a $(a,b)$-coloring of $H$ that
completes the $(a,b)$-coloring $\varphi$ of $G$, hence $H$ is
$(a,b)$-reducible in $G$. ∎

By symmetry and adding the new condition $n_{1}<n_{4}$ in order to fulfill our
convention, we have this lemma:

######  Lemma 31.

Let $n\geq 1$ and $n_{1}<n_{4}$. If $H(n_{1},n_{2},n,n_{3},n_{4})$ is
$(a,b)$-reducible in $G$ and $H(n_{1}+1,n_{2}+1,n-1,n_{3},n_{4})$ is
$(a,b)$-reducible in $G$ when the color-sets of $v_{1},v_{2}$ are
$(n_{1}+n_{2}+2)$-exactly-compatible, then
$H(n_{1}+1,n_{2}+1,n-1,n_{3},n_{4})$ is $(a,b)$-reducible in $G$.

######  Proposition 32.

For any graph $G$, the H-handles $H(2,2,2b-3,2,2)$, $H(1,2,2b-3,3,2)$ and
$H(1,4,2b-3,2,2)$ are the smallest $(2b+1,b)$-reducible H-handles
$H(n_{1},n_{2},n,n_{3},n_{4})$ with $n=2b-3$ in $G$.

###### Proof.

For proving minimality, we have the necessary condition $n_{1}+n_{4}\geq
2b-(2b-3)=3$. Moreover we have $n_{4}<3$. If $n_{1}=1$ then $n_{3}\geq
n_{4}=2$. Therefore $H(1,2,2b-3,2,2)$ could be the smallest
$(2b+1,b)$-reducible handle. However there exists a counter example even for
$H(1,3,2b-3,2,2)$: $C(v_{1})=\\{1,...,b\\}$,
$C(v_{2})=\\{1,...,b-2\\}\cup\\{2b,2b+1\\}$,
$C(v_{4})=\\{b+1,...,2b-1\\}\cup\\{2b+1\\}$, $C(v_{3})=\\{b+1,...,2b\\}$.
Therefore there remain only three configurations to be tested:
$H(1,2,2b-3,3,2)$, $H(1,4,2b-3,2,2)$, and $H(2,2,2b-3,2,2)$. We now consider
each of these three H-handles in turn and prove that it is
$(2b+1,b)$-reducible. Let $n=2b-3$.

#####  $H=H(2,2,2b-3,2,2)$.

Let $\varphi$ be a $(2b+1,b)$-coloring of $G-\mathsf{int}(H)$. We are going to
show that there exist two $(2b-3)$-compatible sets $C$ and $C^{\prime}$ that
can be given to vertices $h_{0}$ and $h_{n}$. By Lemma 22 there exist four
sets $X^{\prime}_{i},i\in\\{1,2,3,4\\}$ for the vertex $h_{n}$ with
$|X^{\prime}_{1}\cap X^{\prime}_{4}|=b-2$. Let
$I=\varphi(v_{1})\cap\varphi(v_{2})$ and
$I^{\prime}=\varphi(v_{3})\cap\varphi(v_{4})$. By hypothesis, both
$\varphi(v_{1})$ and $\varphi(v_{2})$ and $\varphi(v_{3})$ and
$\varphi(v_{4})$ are $4$-compatible. Hence the size of both $I$ and
$I^{\prime}$ is between $b-2$ and $b$. We then consider three cases depending
on the values of $|I|$ and $|I^{\prime}|$.

Case 1.

$|I|=b$ or $|I^{\prime}|=b$. Assume without loss of generality that $|I|=b$.
Then either there exists $i\in\\{1,4\\}$ such that $|I\cap X^{\prime}_{i}|\leq
b-2$ and thus we can set $C=I$ and $C^{\prime}=X^{\prime}_{i}$ or we have
$|I\cap X^{\prime}_{i}|\geq b-1$ for all $i\in\\{1,2,3,4\\}$. In this case we
can set $C=X^{\prime}_{1}$ and $C^{\prime}=X^{\prime}_{4}$.

Case 2.

$|I|=b-1$ or $|I^{\prime}|=b-1$. Assume without loss of generality that
$|I|=b-1$. Since $|X_{1}\cap X_{4}|=b-2$, then there exists $i\in\\{1,4\\}$
such that $|I\cap X^{\prime}_{i}|\leq b-2$ and thus we can set
$C=I\cup\\{x\\}$ and $C^{\prime}=X^{\prime}_{i}$, with
$x\in\\{1,\ldots,a\\}-I-X^{\prime}_{i}$.

Case 3.

$|I|=|I^{\prime}|=b-2$. If there exist $x\in\varphi(v_{1})-I$,
$y\in\varphi(v_{2})-I$ and $i\in\\{1,4\\}$ such that $|(I\cup\\{x,y\\})\cap
X^{\prime}_{i}|\leq b-2$ then we can set $C=I\cup\\{x,y\\}$ and
$C^{\prime}=X^{\prime}_{i}$. Otherwise $|(I\cup\\{x,y\\})\cap
X^{\prime}_{i}|=b-1$, then $X^{\prime}_{1}=\varphi(v_{1})$ and
$X^{\prime}_{4}=\varphi(v_{2})$ then
$\varphi(v_{1})=I\cup\\{x,x^{\prime}\\},\varphi(v_{2})=I\cup\\{y,y^{\prime}\\},\varphi(v_{3})=I\cup\\{x,y\\}$
and $\varphi(v_{4})=I\cup\\{x^{\prime},y^{\prime}\\}$. In this case we can
choose $C=I\cup\\{x,y^{\prime}\\}$ and $C^{\prime}=I\cup\\{x^{\prime},y\\}$.

#####  $H=H(1,2,2b-3,3,2)$.

Let $\varphi$ be a $(2b+1,b)$-coloring of $G-\mathsf{int}(H)$. If
$|\varphi(h_{0})\cap\varphi(h_{n})|\leq b-2$, then $\varphi(h_{0})$ and
$\varphi(h_{n})$ are $(2b-3)$-compatible, therefore by Theorem 19 we conclude.
Else $|\varphi(h_{0})\cap\varphi(h_{n})|>b-2$. By Lemma 23 there exists $I,Y$
and $Z$ such that $|I|=b-2$ and $|Y|=|Z|=2$. Let $Y=Y_{1}\cup Y_{2}$ and
$Z=Z_{1}\cup Z_{2}$, with $|Y_{i}|=|Z_{i}|=1$, $i=1,2$. If there exists
$i,j\in\\{1,2\\}$ such that $|\varphi(h_{0})\cap(I\cup Y_{i}\cup Z_{j})|\leq
b-2$, then we conclude. Otherwise for any $i,j\in\\{1,2\\}$,
$|\varphi(h_{0})\cap(I\cup Y_{i}\cup Z_{j})|>b-2$, then without loss of
generality, $\varphi(h_{0})=I\cup Y$. But Lemma 24 allows to construct another
coloring $\varphi^{\prime}$ with
$|\varphi^{\prime}(h_{0})\cap\varphi(h_{0})|=b-1$ and thus $I\cup
Z\not=\varphi^{\prime}(h_{0})\not=I\cup Y$. Hence there exists
$i,j\in\\{1,2\\}$ such that $|\varphi^{\prime}(h_{0})\cap(I\cup Y_{i}\cup
Z_{j})|\leq b-2$, allowing to conclude.

#####  $H=H(1,4,2b-3,2,2)$.

Let $\varphi$ be a $(2b+1,b)$-coloring of $G-\mathsf{int}(H)$. Then
$\varphi(v_{1})$ and $\varphi(v_{2})$ are $5$-compatible and $\varphi(v_{3})$
and $\varphi(v_{4})$ are $4$-compatible. If
$|\varphi(h_{0})\cap\varphi(h_{n})|\leq b-2$, then $\varphi(h_{0})$ and
$\varphi(h_{n})$ are $(2b-3)$-compatible, therefore by Theorem 19 we conclude.
Else $|\varphi(h_{0})\cap\varphi(h_{n})|>b-2$. By Lemma 22 we have 4 good sets
$X^{\prime}_{1}$, $X^{\prime}_{2}$, $X^{\prime}_{3}$ and $X^{\prime}_{4}$ for
the vertex $h_{n}$, and by Lemma 24, there exists a set $X$ such that
$|X|=b-2$ and a set $Y=\\{y_{1},y_{2},y_{3}\\}$ such that the three good sets
$C_{1}=X\cup\\{y_{1},y_{2}\\}$, $C_{2}=X\cup\\{y_{1},y_{3}\\}$ and
$C_{3}=X\cup\\{y_{2},y_{3}\\}$ can be given to vertex $h_{0}$. If there exists
$i,j\in\\{1,2,3,4\\}$ with $i\neq 4$, such that $|X^{\prime}_{j}\cap
C_{i}|\leq b-2$, then we conclude. Else $\forall i,j\in\\{1,2,3,4\\}$ with
$i\not=4$, we have $b\geq|X^{\prime}_{j}\cap C_{i}|>b-2$, and since
$|X^{\prime}_{1}\cap X^{\prime}_{4}|=b-2$, then for all $j\in\\{1,4\\}$ and
for all $i\in\\{1,2,3\\}$ we have the formula $|X^{\prime}_{j}\cap
C_{i}|=b-1$, so $X^{\prime}_{1}\cap X^{\prime}_{4}\subset C_{i}\subset
X^{\prime}_{1}\cup X^{\prime}_{4}$. Without loss of generality, $y_{1}\in
X^{\prime}_{1}$, thus by the formula with $i=1,j=1$ we have $y_{2}\notin
X^{\prime}_{1}$. Therefore by the formula with $i=3,j=1$ we have $y_{3}\in
X^{\prime}_{1}$, a contradiction with the formula with $i=2,j=1$. ∎

######  Proposition 33.

For any graph $G$, the H-handles $H(2,3,2b-4,3,2)$, $H(2,2,2b-4,4,2)$,
$H(2,2,2b-4,3,3)$, $H(1,2,2b-4,4,3)$, and $H(1,4,2b-4,3,3)$ are the smallest
$(2b+1,b)$-reducible H-handles $H(n_{1},n_{2},n,n_{3},n_{4})$ with $n=2b-4$ in
$G$.

###### Proof.

For proving minimality, we have the necessary condition $n_{1}+n_{4}\geq
2b-(2b-4)=4$. Moreover we have $n_{1}\leq n_{4}<4$. If $n_{1}=1$ then
$n_{3}\geq n_{4}=3$ ; if $n_{2}\leq 3$ then we can construct a simple counter
example for $H(1,3,2b-4,3,3)$: $C(v_{1})=\\{1,...,b\\}$,
$C(v_{2})=\\{3,...,b+2\\}$, $C(v_{4})=\\{b+3,...,2b+1\\}\cup\\{b+1\\}$,
$C(v_{3})=\\{b+2,...,2b+1\\}$. Therefore there remain two possibilities for
$n_{1}=1$: $H(1,2,2b-4,4,3)$ and $H(1,4,2b-4,3,3)$.

If $n_{1}=3$, then $H(3,3,2b-4,3,3)$ could be the smallest, but this case is a
subcase of $n_{1}=2$. If $n_{1}=2$, then $H(2,2,2b-4,2,2)$ could be the
smallest, however there exists a counter example even for $H(2,2,2b-4,3,2)$:
$C(v_{1})=\\{1,...,b\\}$, $C(v_{2})=\\{2,...,b+1\\}$,
$C(v_{4})=\\{b+2,...,2b+1\\}$ and $C(v_{3})=\\{2,...,b\\}\cup\\{2b,2b+1\\}$.
Therefore there remain three possibilities for $n_{1}=2$: $H(2,3,2b-4,3,2)$,
$H(2,2,2b-4,4,2)$ and $H(2,2,2b-4,3,3)$. We consider each remaining H-handle
in turn and prove that it is $(2b+1,b)$-reducible in $G$.

#####  $H=H(2,3,2b-4,3,2)$.

Let $\varphi$ be a $(2b+1,b)$-coloring of $G-\mathsf{int}(H)$. We note
$C_{0}=\varphi(v_{1})$, $C_{5}=\varphi(v_{2})$,
$C^{\prime}_{0}=\varphi(v_{4})$ and $C^{\prime}_{5}=\varphi(v_{3})$, then both
$C_{0}$, $C_{5}$ and $C^{\prime}_{0}$, $C^{\prime}_{5}$ are 5-compatible. By
Lemma 23, there exists three sets $I$, $Y=Y_{1}\cup Y_{2}$ and $Z=Z_{1}\cup
Z_{2}$, such that $|I|=b-2$ and $|Y_{i}|=|Z_{i}|=1$ for $i=1,2$, such that for
any $i,j\in\\{1,2\\}$, the set $C_{2}=I\cup Y_{i}\cup Z_{j}$ can be given to
vertex $h_{0}$. Similarly, by Lemma 23, there exists three sets $I^{\prime}$,
$Y^{\prime}=Y^{\prime}_{1}\cup Y^{\prime}_{2}$ and
$Z^{\prime}=Z^{\prime}_{1}\cup Z^{\prime}_{2}$, such that $|I^{\prime}|=b-2$
and $|Y^{\prime}_{i}|=|Z^{\prime}_{i}|=1$ for $i=1,2$, such that for any
$i,j\in\\{1,2\\}$, the set $C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{i}\cup
Z^{\prime}_{j}$ can be given to vertex $h_{n}$. We are going to show that
there is a choice of the indices such that $C_{2}$, $C^{\prime}_{2}$ are
$(2b-4)$-compatible, i.e., $|C_{2}\cap C^{\prime}_{2}|\geq 2$.

Case 1.

$|I\cap I^{\prime}|\geq 2$. We set $C_{2}=I\cup Y_{1}\cup Z_{1}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup Z^{\prime}_{1}$.

Case 2.

$|I\cap I^{\prime}|=1$. If $Y_{1}\subset I^{\prime}$, then we set $C_{2}=I\cup
Y_{1}\cup Z_{1}$ and $C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup
Z^{\prime}_{1}$. We proceed similarly if $Y_{2}\subset I^{\prime}$ or
$Z_{i}\subset I^{\prime}$. Otherwise we have $|I^{\prime}\cap(Y\cup Z)|=0$ and
thus $|I\cup Y\cup Z\cup I^{\prime}|=2b-1$. Proceeding in a similar way with
$I,Y^{\prime}$ and $Z^{\prime}$, thus we can assume that $|I\cap
Y^{\prime}\cup Z^{\prime}|=0$. Hence $|(Y\cup Z)\cap(Y^{\prime}\cup
Z^{\prime})|\geq 1$ and thus there exists $t\in(Y\cup Z)\cap(Y^{\prime}\cup
Z^{\prime})$, let say w.l.o.g. that $t\in Y\cup Y^{\prime}$. Then set
$C_{2}=I\cup\\{t\\}\cup Z_{1}$ and $C^{\prime}_{2}=I^{\prime}\cup\\{t\\}\cup
Z^{\prime}_{1}$.

Case 3.

$|I\cap I^{\prime}|=0$. If $Y_{1}\subset I^{\prime}$, and $Z_{1}\subset
I^{\prime}$, then we set $C_{2}=I\cup Y_{1}\cup Z_{1}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup Z^{\prime}_{1}$. We proceed
similarly for the other pairs of sets among $Y_{1},Y_{2},Z_{1},Z_{2}$, and by
symmetry for the pairs of sets among
$Y^{\prime}_{1},Y^{\prime}_{2},Z^{\prime}_{1},Z^{\prime}_{2}$ and $I$. If
$Y\subset I^{\prime}$ and $Z\cap I^{\prime}=\emptyset$, since $|I\cup Y\cup
Z\cup I^{\prime}|=2b-2=a-3$ then $|I\cap(Y^{\prime}\cup Z^{\prime})|\geq 1$
and without loss of generality $Y^{\prime}_{i}\subset I$. Then we set
$C_{2}=I\cup Y_{1}\cup Z_{1}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{i}\cup Z^{\prime}_{1}$. By symmetry we proceed similarly for
$Z\subset I^{\prime}$, $Y^{\prime}\subset I$ and $Z^{\prime}\subset I$.
Otherwise $|I^{\prime}\cap(Y\cup Z)|\leq 1$ and $|I\cap(Y^{\prime}\cup
Z^{\prime})|\leq 1$. If $|I^{\prime}\cap(Y\cup Z)|=1$ and
$|I\cap(Y^{\prime}\cup Z^{\prime})=1$, then w.l.o.g. $Y_{i}\subset I^{\prime}$
and $Z^{\prime}_{j}\subset I$ and we set $C_{2}=I\cup Y_{i}\cup Z_{1}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup Z^{\prime}_{j}$. If
$|I^{\prime}\cap(Y\cup Z)|=1$ and $|I\cap(Y^{\prime}\cup Z^{\prime})=0$, then
w.l.o.g. $Y_{1}\subset I^{\prime}$. Since $|I\cup I^{\prime}|=a-5$, so
$|Z\cap(Y^{\prime}\cup Z^{\prime})|\geq 1$. Then w.l.o.g.
$Z_{1}=Y^{\prime}_{j}$, therefore we set $C_{2}=I\cup Y_{1}\cup Z_{1}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{j}\cup Z^{\prime}_{1}$. By symmetry
we proceed similarly for $|I^{\prime}\cap(Y\cup Z)|=0$ and
$|I\cap(Y^{\prime}\cup Z^{\prime})=1$. Otherwise $|I^{\prime}\cap(Y\cup Z)|=0$
and $|I\cap(Y^{\prime}\cup Z^{\prime})=0$. Since $|I\cup I^{\prime}|=a-5$ and
$|(Y\cup Z)|=|(Y^{\prime}\cup Z^{\prime})|=4$ , then $|(Y\cup
Z)\cap(Y^{\prime}\cup Z^{\prime})|\geq 3$. Thus w.l.o.g. $Y\cup Z_{1}\subset
Y^{\prime}\cup Z^{\prime}$ and $Z_{1}\subset Z^{\prime}$, so there exists
$i\in\\{1,2\\}$ such that $Y_{i}\subset Y^{\prime}$. We then set $C_{2}=I\cup
Y_{i}\cup Z_{1}$ and $C^{\prime}_{2}=I^{\prime}\cup Y_{i}\cup Z_{1}$.

#####  $H=H(2,2,2b-4,4,2)$.

Let $\varphi$ be a $(2b+1,b)$-coloring of $G-\mathsf{int}(H)$. We note
$C_{0}=\varphi(v_{1})$, $C_{4}=\varphi(v_{2})$,
$C^{\prime}_{0}=\varphi(v_{4})$ and $C^{\prime}_{6}=\varphi(v_{3})$. Let
$I=C_{0}\cap C_{4}$ and $I^{\prime}=C^{\prime}_{0}\cap C^{\prime}_{6}$. Then,
as $C_{0}$, $C_{4}$ are 4-compatible and $C^{\prime}_{0}$, $C^{\prime}_{6}$
are 6-compatible, we have $|I|\geq b-2$ and $|I^{\prime}|\geq b-3$. We are
going to show that there exist two sets of $b$ colors $C_{2}$ and
$C^{\prime}_{2}$ that can be given to vertices $h_{0}$ and $h_{n}$,
respectively. By Lemma 22 there exist two sets $X_{1}$ and $X_{4}$ such that
$|X_{1}\cap X_{4}|=b-2$ for $C_{2}$. Also, by Lemma 23, there exists three
sets $J$, $Y=Y_{1}\cup Y_{2}$ and $Z=Z_{1}\cup Z_{2}$, such that $|J|=b-2$,
$|Y_{i}|=|Z_{i}|=1$ for $i=1,2$, and for any $i,j\in\\{1,2\\}$, we can set
$C^{\prime}_{2}=J\cup Y_{i}\cup Z_{j}$. We now consider ten cases depending on
the values of $|I|$ and $|I^{\prime}|$.

Case 1.

$|I^{\prime}|=b$. Since $|X_{1}\cup X_{4}|=b+2$, then without lost of
generality there exists $Y\subset I^{\prime}\cap X_{1}$ such that $|Y|=1$. We
choose $I^{\prime\prime}$ such that $Y\subset I^{\prime\prime}\subset
I^{\prime}$ and $|I^{\prime\prime}|=b-1$, and we choose any $z\in
X_{1}-I^{\prime\prime}$. Then we set $C_{2}=X_{1}$ and
$C^{\prime}_{2}=I^{\prime\prime}\cup\\{z\\}$.

Case 2.

$|I^{\prime}|=b-1$ and $|I|=b$. If $|I^{\prime}\cap C_{0}|\geq 1$, we choose
any $z\in C_{0}-I^{\prime}$, then we set $C_{2}=C_{0}$ and
$C^{\prime}_{2}=I^{\prime}\cup\\{z\\}$. Else we have $I^{\prime}\cap
C_{0}=\emptyset$ and we choose any $y_{1},y_{2}\in C_{0}$ and any $z_{1}\in
I^{\prime}$. Then we set $C_{2}=\\{z_{1}\\}\cup(C_{0}-\\{y_{1}\\})$ and
$C^{\prime}_{2}=I^{\prime}\cup\\{y_{2}\\}$.

Case 3.

$|I|=|I^{\prime}|=b-1$. If $|I^{\prime}\cap C_{0}|\geq 1$, we choose any $z\in
C_{0}-I^{\prime}$ and we set $C_{2}=C_{0}$ and
$C^{\prime}_{2}=I^{\prime}\cup\\{z\\}$. We do the same if $|I^{\prime}\cap
C_{4}|\geq 1$. Else we have $I^{\prime}\cap(C_{0}\cup C_{4})=\emptyset$ and we
choose any $y_{2}\in I$ and any $z_{1}\in I^{\prime}$. Then we set
$C_{2}=I\cup\\{z_{1}\\}$ and $C^{\prime}_{2}=I^{\prime}\cup\\{y_{2}\\}$.

Case 4.

$|I|=b-2$ and $|I^{\prime}|=b-1$. We note $C_{0}-C_{4}=Y_{1}\cup Y_{2}$ and
$C_{4}-C_{0}=Z_{1}\cup Z_{2}$, with $|Y_{i}|=|Z_{i}|=1$, $i=1,2$. If
$|C^{\prime}_{0}\cap I|\geq 2$, then we set $C_{2}=I\cup Y_{1}\cup Z_{1}$ and
$C^{\prime}_{2}=C^{\prime}_{0}$. If $|I^{\prime}\cap I|=1$, then we choose any
$X\subset I-I^{\prime}$ such that $|X|=1$ and we set $C_{2}=I\cup Y_{1}\cup
Z_{1}$ and $C^{\prime}_{2}=I^{\prime}\cup X$. Else $|I^{\prime}\cap I|=0$. If
there exists $i,j\in\\{1,2\\}$ such that $Y_{i},Z_{j}\in C^{\prime}_{0}$, then
we set $C_{2}=I\cup Y_{i}\cup Z_{j}$ and $C^{\prime}_{2}=C^{\prime}_{0}$. Else
without lost of generality $Y_{1}\subset C^{\prime}_{0}$, hence we choose any
$X\subset C^{\prime}_{0}-Y_{1}$ such that $|X|=1$ and we set $C_{2}=I\cup
Y_{1}\cup Z_{1}$ and $C^{\prime}_{2}=(C^{\prime}_{0}-X)\cup Z_{1}$.

Case 5.

$|I|=b$ and $|I^{\prime}|=b-2$. We note
$C^{\prime}_{0}-C^{\prime}_{6}=Y^{\prime}_{1}\cup Y^{\prime}_{2}$. If
$|I^{\prime}\cap C_{0}|\geq 1$, we choose $X\subset C_{0}-I^{\prime}$ such
that $|X|=1$ and we set $C_{2}=C_{0}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{1}\cup X$. Otherwise $|I^{\prime}\cap C_{0}|=0$ and we choose
$X,X^{\prime}\subset C_{0}$ such that $|X^{\prime}|=|X|=1$ and
$X^{\prime\prime}\subset I^{\prime}$ such that $|X^{\prime\prime}|=1$. Then we
set $C_{2}=(C_{0}-X^{\prime})\cup X^{\prime\prime}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup X$.

Case 6.

$|I|=b-1$ and $|I^{\prime}|=b-2$. We note
$C^{\prime}_{0}-C^{\prime}_{6}=Y^{\prime}_{1}\cup Y^{\prime}_{2}$. If
$|I^{\prime}\cap C_{0}|\geq 1$, we choose $X\subset C_{0}-I^{\prime}$ such
that $|X|=1$ and we set $C_{2}=C_{0}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{1}\cup X$. Otherwise $|I^{\prime}\cap C_{0}|=0$ and we choose
$X\subset I$ such that $|X|=1$ and $X^{\prime\prime}\subset I^{\prime}$ such
that $|X^{\prime\prime}|=1$. Then we set $C_{2}=I\cup X^{\prime\prime}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup X$.

Case 7.

$|I|=|I^{\prime}|=b-2$. We note $C_{0}-C_{4}=Y_{1}\cup Y_{2}$,
$C_{4}-C_{0}=Z_{1}\cup Z_{2}$ and
$C^{\prime}_{0}-C^{\prime}_{6}=Y^{\prime}_{1}\cup Y^{\prime}_{2}$. If
$I^{\prime}=I$, we choose $X\in\\{Y_{1},Z_{1}\\}-Y^{\prime}_{1}$ and we set
$C_{2}=I\cup Y_{1}\cup Z_{1}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{1}\cup X$. If $I^{\prime}\not=I$ and $|I^{\prime}\cap I|\geq 1$,
we choose $X\subset I-I^{\prime}-Y^{\prime}_{1}$ such that $|X|=1$ or if
$Y^{\prime}_{1}\subset I$ we choose $X=Y^{\prime}_{2}$. Then we set
$C_{2}=I\cup Y_{1}\cup Z_{1}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{1}\cup X$. Otherwise $|I^{\prime}\cap I|=0$. If there exists
$Y_{i}\subset I^{\prime}\cup Y^{\prime}_{1}$, then we choose $X\subset
I-Y^{\prime}_{1}$ such that $|X|=1$ or if $Y^{\prime}_{1}=I$ we choose
$X=Y^{\prime}_{2}$. Then we set $C_{2}=I\cup Y_{i}\cup Z_{1}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup X$. We proceed similarly for
$Z_{j}\subset I^{\prime}\cup Y^{\prime}_{1}$. Otherwise $(C_{0}\cup
C_{4})\cap(I^{\prime}\cup Y^{\prime}_{1})=\emptyset$ and thus
$Y^{\prime}_{2}\subset C_{0}\cup C_{4}$. If $Y^{\prime}_{2}\in C_{0}$ then we
choose $Y_{i}=Y^{\prime}_{2}$, else $Y_{i}=Y_{1}$. If $Y^{\prime}_{2}\in
C_{4}$ then we choose $Z_{j}=Y^{\prime}_{2}$, else $Z_{j}=Z_{1}$. If
$I\not=Y^{\prime}_{2}$ then we choose $X\subset I-Y^{\prime}_{2}$ such that
$|X|=1$. If $I=Y^{\prime}_{2}$ then we choose $X=Y_{i}$. Finally, we set
$C_{2}=I\cup Y_{i}\cup Z_{j}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{2}\cup X$.
For the three next cases, we note
$I^{\prime}(2)=C^{\prime}_{0}-C^{\prime}_{6}=Y^{\prime}_{1}\cup
Y^{\prime}_{2}\cup Y^{\prime}_{3}$ and
$G=C^{\prime}_{6}-C^{\prime}_{0}=Z^{\prime}_{1}\cup Z^{\prime}_{2}\cup
Z^{\prime}_{3}$.

Case 8.

$|I|=b$ and $|I^{\prime}|=b-3$. If $|I^{\prime}\cap C_{0}|\geq 1$, then we
choose $X\subset C_{0}-I^{\prime}$ such that $|X|=1$. If
$|I^{\prime}-C_{0}|\geq 1$ then we choose $X^{\prime}\subset I^{\prime}-C_{0}$
such that $|X^{\prime}|=1$. If $I^{\prime}\subset C_{0}$ then we choose
$X^{\prime}=Y^{\prime}_{1}$ if $|Y^{\prime}_{1}\cap C_{0}|=0$ and
$X^{\prime}=X$ otherwise. Then we set $C_{2}=C_{0}-X\cup X^{\prime}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup Y^{\prime}_{2}\cup
Z^{\prime}_{1}$. If $|I^{\prime}\cap C_{0}|=0$, then
$|C_{0}\cap(I^{\prime}(2)\cup I^{\prime}(3)|\geq 2$ and there exist
$i,j,k\in\\{1,2,3\\}$ such that $|(Y^{\prime}_{i}\cup Y^{\prime}_{j}\cup
Z^{\prime}_{k})\cap C_{0}|\geq 1$. We set $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{i}\cup Y^{\prime}_{j}\cup Z^{\prime}_{k}$. If
$C_{0}=C^{\prime}_{2}$ then we set $C_{2}=C_{0}$. If
$C_{0}\not=C^{\prime}_{2}$, then we choose $X\subset C_{0}-C^{\prime}_{2}$ and
$X^{\prime}\subset C^{\prime}_{2}-C_{0}$ such that $|X^{\prime}|=|X|=1$ and we
set $C_{2}=C_{0}-X\cup X^{\prime}$.

Case 9.

$|I|=b-1$ and $|I^{\prime}|=b-3$. If $|I^{\prime}\cap I|\geq 1$ then we choose
$X=Y^{\prime}_{1}$ if $|Y^{\prime}_{1}\cap I|=0$ and $X=C_{0}-C_{4}$
otherwise. Then we set $C_{2}=I\cup X$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{1}\cup Y^{\prime}_{2}\cup Z^{\prime}_{1}$. If $|I^{\prime}\cap
I|=0$, then $|I\cap(I^{\prime}(2)\cup I^{\prime}(3)|\geq 1$ and there exist
$i,j,k\in\\{1,2,3\\}$ such that $|(Y^{\prime}_{i}\cup Y^{\prime}_{j}\cup
Z^{\prime}_{k})\cap I|\geq 1$. We set $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{i}\cup Y^{\prime}_{j}\cup Z^{\prime}_{k}$ and we choose $X\subset
C^{\prime}_{2}-I$ such that $|X|=1$ and set $C_{2}=I\cup X$.

Case 10.

$|I|=b-2$ and $|I^{\prime}|=b-3$. We note $C_{0}-C_{4}=Y_{1}\cup Y_{2}$ and
$C_{4}-C_{0}=Z_{1}\cup Z_{2}$. If $|I^{\prime}\cap I|\geq 2$, then we set
$C_{2}=I\cup Y_{1}\cup Z_{1}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{1}\cup Y^{\prime}_{2}\cup Z^{\prime}_{1}$. If $|I^{\prime}\cap
I|=1$ and $Y_{i}$ or $Z_{j}\in I^{\prime}$, then we set $C_{2}=I\cup Y_{i}\cup
Z_{j}$ and $C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup
Y^{\prime}_{2}\cup Z^{\prime}_{1}$. If $|I^{\prime}\cap
I|=|I^{\prime}\cap(C_{0}\cup C_{4})|=1$, then $|(I^{\prime}(2)\cup
I^{\prime}(3))\cap(C_{0}\cup C_{4})|\geq 1$, so there exist $i,j\in\\{1,2\\}$
and $i^{\prime},i^{\prime\prime},j^{\prime}\in\\{1,2,3\\}$ such that
$|(Y^{\prime}_{i^{\prime}}\cup Y^{\prime}_{i^{\prime\prime}}\cup
Z^{\prime}_{j^{\prime}})\cap(I\cup Y_{i}\cup Z_{j})|\geq 1$. Therefore we set
$C_{2}=I\cup Y_{i}\cup Z_{j}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{i^{\prime}}\cup Y^{\prime}_{i^{\prime\prime}}\cup
Z^{\prime}_{j^{\prime}}$. Otherwise $|I^{\prime}\cap I|=0$. If $Y_{i},Z_{j}\in
I^{\prime}$, then we set $C_{2}=I\cup Y_{i}\cup Z_{j}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup Y^{\prime}_{2}\cup
Z^{\prime}_{1}$. If $Y_{i}\in I^{\prime}$ and
$|I^{\prime}\cap(C_{4}-C_{0})|=0$, then $|I^{\prime}\cap C_{4}|=0$ and
$|(I^{\prime}(2)\cup I^{\prime}(3))\cap C_{4}|\geq(b+b-3)+6-a=2$. So there
exist $j\in\\{1,2\\}$ and
$i^{\prime},i^{\prime\prime},j^{\prime}\in\\{1,2,3\\}$ such that
$|(Y^{\prime}_{i^{\prime}}\cup Y^{\prime}_{i^{\prime\prime}}\cup
Z^{\prime}_{j^{\prime}})\cap(I\cup Z_{j})|\geq 1$. Therefore we set
$C_{2}=I\cup Y_{i}\cup Z_{j}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{i^{\prime}}\cup Y^{\prime}_{i^{\prime\prime}}\cup
Z^{\prime}_{j^{\prime}}$. We proceed similarly if $Z_{j}\in I^{\prime}$ and
$|I^{\prime}\cap C(2)|=0$. Else $|I^{\prime}\cap(C_{0}\cup C_{4})|=0$, so
$|(I^{\prime}(2)\cup I^{\prime}(3))\cap(C_{0}\cup C_{4})|\geq b+2+6+b-3-a=4$.
If $Y^{\prime}_{i^{\prime}},Y^{\prime}_{i^{\prime\prime}}\in I$, then we set
$C_{2}=I\cup Y_{1}\cup Z_{1}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{i^{\prime}}\cup Y^{\prime}_{i^{\prime\prime}}\cup Z^{\prime}_{1}$.
If $Y^{\prime}_{i^{\prime}},Z^{\prime}_{j^{\prime}}\in I$, then we set
$C_{2}=I\cup Y_{1}\cup Z_{1}$ and $C^{\prime}_{2}=I^{\prime}\cup
Y^{\prime}_{i^{\prime}}\cup Y^{\prime}_{i^{\prime\prime}}\cup
Z^{\prime}_{j^{\prime}}$. If $|I\cap I^{\prime}(2)|=1$ and $|I\cap
I^{\prime}(3)|=0$, we note $Y^{\prime}_{i^{\prime}}\subset I$, and thus
$|((I^{\prime}(2)-Y^{\prime}_{i^{\prime}})\cup I^{\prime}(3))\cap(C(2)\cup
C(3))|\geq 4-1=3$. Hence there exist $i,j\in\\{1,2\\}$ and
$i^{\prime\prime},j^{\prime}\in\\{1,2,3\\}$ such that
$|(Y^{\prime}_{i^{\prime\prime}}\cup Z^{\prime}_{j^{\prime}})\cap(Y_{i}\cup
Z_{j})|\geq 1$, therefore we set $C_{2}=I\cup Y_{i}\cup Z_{j}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{i^{\prime}}\cup
Y^{\prime}_{i^{\prime\prime}}\cup Z^{\prime}_{j^{\prime}}$. If $|I\cap
I^{\prime}(2)|=0$ and $|I\cap I^{\prime}(3)|=0$, then $C(2)\cup C(3)\subset
C^{\prime}_{0}\cup C^{\prime}_{6}$ and $|(C(2)\cup C(3))-I^{\prime}(3)|\geq
1$, so there exist $i,j\in\\{1,2\\}$ and
$i^{\prime},i^{\prime\prime},j^{\prime}\in\\{1,2,3\\}$ such that
$|(I^{\prime}\cup Y^{\prime}_{i^{\prime}}\cup
Y^{\prime}_{i^{\prime\prime}}\cup Z^{\prime}_{j^{\prime}})\cap(Y_{i}\cup
Z_{j})|=2$, therefore we set $C_{2}=I\cup Y_{i}\cup Z_{j}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{i^{\prime}}\cup
Y^{\prime}_{i^{\prime\prime}}\cup Z^{\prime}_{j^{\prime}}$. If $|I\cap
I^{\prime}(2)|=0$ and $|I\cap I^{\prime}(3)|\geq 1$, we note
$Z^{\prime}_{j^{\prime}}\subset I$, so $|(C(2)\cup C(3))\cap
C^{\prime}_{0}|\geq 4+b+b-2-a=3$ and there exists $i,j\in\\{1,2\\}$ and
$i^{\prime},i^{\prime\prime}\in\\{1,2,3\\}$ such that $|(I^{\prime}\cup
Y^{\prime}_{i^{\prime}}\cup Y^{\prime}_{i^{\prime\prime}})\cap(Y_{i}\cup
Z_{j})|\geq 1$, therefore we set $C_{2}=I\cup Y_{i}\cup Z_{j}$ and
$C^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{i^{\prime}}\cup
Y^{\prime}_{i^{\prime\prime}}\cup Z^{\prime}_{j^{\prime}}$.

#####  $H=H(2,2,2b-4,3,3)$.

Let $\varphi$ be a $(2b+1,b)$-coloring of $G-\mathsf{int}(H)$. We note
$C_{0}=\varphi(v_{1})$, $C_{4}=\varphi(v_{2})$,
$C^{\prime}_{0}=\varphi(v_{4})$ and $C^{\prime}_{6}=\varphi(v_{3})$, then
$C_{0},C_{4}$ are 4-compatible and $C^{\prime}_{0},C^{\prime}_{6}$ are
6-compatible. By Proposition 28, $H(1,1,2b-3,3,3)$ is $(2b+1,b)$-reducible,
and by Lemma 31 there only remains to prove that $H$ is reducible when
$C_{0},C_{4}$ are 4-exactly-compatible. We are going to show that there exist
two sets of $b$ colors $C_{2}$ and $C^{\prime}_{3}$ that can be given to
vertices $h_{0}$ and $h_{n}$, respectively. We note $I=C_{0}\cap C_{4}$,
$I^{\prime}=C^{\prime}_{0}\cap C^{\prime}_{6}$, $C_{0}-C_{4}=Y_{1}\cup Y_{2}$
and $C_{4}-C_{0}=Z_{1}\cup Z_{2}$ with $|Y_{i}|=|Z_{i}|=1$.

Case 1.

$|I^{\prime}|\geq b-2$. We set $C_{2}=I\cup Y_{1}\cup Z_{1}$. We choose
$I^{\prime\prime}\subset I^{\prime}$ such that $|I^{\prime\prime}|=b-2$ and we
choose $X\subset C_{2}-I^{\prime\prime}$ such that $|X|=2$, then we set
$C^{\prime}_{3}=I^{\prime\prime}\cup X$.

Case 2.

$|I^{\prime}|=b-3$. We note $C^{\prime}_{0}-C^{\prime}_{6}=Y^{\prime}_{1}\cup
Y^{\prime}_{2}\cup Y^{\prime}_{3}$,
$C^{\prime}_{6}-C^{\prime}_{0}=Z^{\prime}_{1}\cup Z^{\prime}_{2}\cup
Z^{\prime}_{3}$, $D_{1}=I\cup Y_{1}\cup Z_{1}$, $D_{2}=I\cup Y_{1}\cup Z_{2}$,
$D_{3}=I\cup Y_{2}\cup Z_{1}$, $D_{4}=I\cup Y_{2}\cup Z_{2}$,
$D^{\prime}_{1}=I^{\prime}\cup Y^{\prime}_{1}\cup Y^{\prime}_{2}\cup
Z^{\prime}_{1}$, $D^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{1}\cup
Y^{\prime}_{3}\cup Z^{\prime}_{2}$ and $D^{\prime}_{3}=I^{\prime}\cup
Y^{\prime}_{2}\cup Y^{\prime}_{3}\cup Z^{\prime}_{3}$. For any
$i\in\\{1,2,3,4\\}$ and $j\in\\{1,2,3\\}$, if $|D^{\prime}_{j}\cap D_{i}|\geq
2$, then we set $C_{2}=D_{i}$ and $C^{\prime}_{3}=D^{\prime}_{j}$. Otherwise
for any $i\in\\{1,2,3,4\\}$ and $j\in\\{1,2,3\\}$ we have $|D^{\prime}_{j}\cap
D_{i}|\leq 1$, since $|(C_{0}\cup C_{4})\cap D^{\prime}_{j}|\geq b+2+b-a=1$.
If $|(C_{0}\cup C_{4})\cap D^{\prime}_{1}|=1$, so $Y^{\prime}_{3}\cup
Z^{\prime}_{2}\cup Z^{\prime}_{3}\subset C_{0}\cup C_{4}$, a contradiction
with $D^{\prime}_{2}$ and $D^{\prime}_{3}$. Proceeding similarly for
$D^{\prime}_{2}$ and $D^{\prime}_{3}$ we are in the case that for any
$j\in\\{1,2,3\\}$, $|(C_{0}\cup C_{4})\cap D^{\prime}_{j}|=2$. Then, without
loss of generality, $C_{0}-C_{4}\subset D^{\prime}_{1}$ and if
$C_{4}-C_{0}\subset D^{\prime}_{2}$ then $C_{0}-C_{4}=Y^{\prime}_{2}\cup
Z^{\prime}_{1}$ and $C_{4}-C_{0}=Y^{\prime}_{3}\cup Z^{\prime}_{2}$, a
contradiction with $D^{\prime}3$. Else, by symmetry, $C_{0}-C_{4}\subset
D^{\prime}_{1}\cap D^{\prime}_{2}\cap D^{\prime}_{3}=I^{\prime}$, then
$|I\cup(C_{4}-C_{0})\cup C^{\prime}_{0}\cup C^{\prime}_{6}|=b-2+2+b+3=a+2>a$,
a contradiction.

#####  $H=H(1,2,2b-4,4,3)$.

Let $\varphi$ be a $(2b+1,b)$-coloring of $G-\mathsf{int}(H)$. We note
$C_{0}=\varphi(v_{1})$, $C_{3}=\varphi(v_{2})$,
$C^{\prime}_{0}=\varphi(v_{4})$ and $C^{\prime}_{7}=\varphi(v_{3})$, then
$C_{0},C_{3}$ are $3$-compatible, and $C^{\prime}_{0},C^{\prime}_{7}$ are
7-compatible. By Proposition 32, $H(1,2,2b-3,3,2)$ is $(2b+1,b)$-reducible,
and by Lemma 30, there only remains to prove that $H$ is reducible in the case
$C^{\prime}_{0},C^{\prime}_{7}$ are $7$-exactly-compatible. We are going to
show that there exist two sets of $b$ colors $C_{1}$ and $C^{\prime}_{3}$ that
can be given to vertices $h_{0}$ and $h_{n}$, respectively. We note
$C^{\prime}_{0}\cap C^{\prime}_{7}=Y^{\prime}_{1}\cup Y^{\prime}_{2}\cup
Y^{\prime}_{3}$, $I^{\prime}=C^{\prime}_{7}-C^{\prime}_{0}$,
$I^{\prime\prime}=\\{1,\ldots,2b+1\\}-C^{\prime}_{7}-C^{\prime}_{0}=Z^{\prime}_{1}\cup
Z^{\prime}_{2}\cup Z^{\prime}_{3}\cup Z^{\prime}_{4}$,
$D^{\prime}_{1}=I^{\prime}\cup Y^{\prime}_{1}\cup Z^{\prime}_{1}\cup
Z^{\prime}_{2}$, $D^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{2}\cup
Z^{\prime}_{3}\cup Z^{\prime}_{4}$, $D^{\prime}_{3}=I^{\prime}\cup
Y^{\prime}_{3}\cup Z^{\prime}_{1}\cup Z^{\prime}_{4}$ and
$D^{\prime}_{4}=I^{\prime}\cup Y^{\prime}_{2}\cup Z^{\prime}_{2}\cup
Z^{\prime}_{3}$. By Lemma 24 there exist two (distinct) good sets $D_{1}$ and
$D_{2}$, for $C_{1}$. If there exists $i\in\\{1,2\\}$ and $j\in\\{1,2,3,4\\}$
such that $|D^{\prime}_{j}\cap D_{i}|\geq 2$, then we set $C_{1}=D_{i}$ and
$C^{\prime}_{3}=D^{\prime}_{j}$. Else for any $i\in\\{1,2\\}$ and
$j\in\\{1,2,3,4\\}$ we have $|D^{\prime}_{j}\cap D_{i}|\leq 1$. However
$|(D^{\prime}_{1}\cup D^{\prime}_{2}\cup D^{\prime}_{3})\cap D_{i}|\geq
b+4+b-a=3$ and $|(D^{\prime}_{1}\cup D^{\prime}_{4}\cup D^{\prime}_{3})\cap
D_{i}|\geq 3$. Thus $|D^{\prime}_{j}\cap D_{i}|=1$ and $|(D^{\prime}_{1}\cup
D^{\prime}_{2}\cup D^{\prime}_{3})\cap D_{i}|=|(D^{\prime}_{1}\cup
D^{\prime}_{4}\cup D^{\prime}_{3})\cap D_{i}|=3$. Then for any $i=1,2$,
$C^{\prime}_{0}\cap C^{\prime}_{7}\subset D_{i}$ and $D_{i}\cap(I^{\prime}\cup
I^{\prime\prime})=\emptyset$, and therefore $D_{i}=C^{\prime}_{0}$, a
contradiction with $D_{1}\not=D_{2}$.

#####  $H=H(1,4,2b-4,3,3)$.

Let $\varphi$ be a $(2b+1,b)$-coloring of $G-\mathsf{int}(H)$, we note
$C_{0}=\varphi(v_{1})$, $C_{5}=\varphi(v_{2})$,
$C^{\prime}_{0}=\varphi(v_{4})$ and $C^{\prime}_{6}=\varphi(v_{n})$, then
$C_{0},C_{5}$ are 5-compatible and $C^{\prime}_{0},C^{\prime}_{6}$ are
6-compatible. By Proposition 32, $H(1,4,2b-3,2,2)$ is $(2b+1,b)$-reducible
and, by Lemma 30, there only remains to prove the reduction for the case
$C^{\prime}_{0},C^{\prime}_{6}$ are 6-exactly-compatible. We are going to show
that there exist two sets of $b$ colors $C_{1}$ and $C^{\prime}_{3}$ that can
be given to vertices $h_{0}$ and $h_{n}$, respectively. We note
$C^{\prime}_{0}-C^{\prime}_{6}=Y^{\prime}_{1}\cup Y^{\prime}_{2}\cup
Y^{\prime}_{3}$, $C^{\prime}_{6}-C^{\prime}_{0}=Z^{\prime}_{1}\cup
Z^{\prime}_{2}\cup Z^{\prime}_{3}$,
$I^{\prime}=\\{1,\ldots,2b+1\\}-C^{\prime}_{6}-C^{\prime}_{0}$,
$D^{\prime}_{1}=I^{\prime}\cup Y^{\prime}_{1}\cup Z^{\prime}_{1}$,
$D^{\prime}_{2}=I^{\prime}\cup Y^{\prime}_{2}\cup Z^{\prime}_{2}$ and
$D^{\prime}_{3}=I^{\prime}\cup Y^{\prime}_{3}\cup Z^{\prime}_{3}$. By Lemma 24
there exist $I$ such that $|I|=b-2$, and $X=X_{1}\cup X_{2}\cup X_{3}$ such
that $D_{1}=I\cup X_{1}\cup X_{2}$, $D_{2}=I\cup X_{1}\cup X_{3}$ and
$D_{3}=I\cup X_{2}\cup X_{3}$. For any $i,j\in\\{1,2,3\\}$, if
$|D^{\prime}_{j}\cap D_{i}|\geq 2$, then we set $C_{1}=D_{i}$ and
$C^{\prime}_{3}=D^{\prime}_{j}$. Else for any $i,j\in\\{1,2,3\\}$ we have
$|D^{\prime}_{j}\cap D_{i}|\leq 1$. However $|(D^{\prime}_{1}\cup
D^{\prime}_{2}\cup D^{\prime}_{3})\cap D_{i}|\geq b+3+b-a=2$. Thus $I\cap
I^{\prime}=\emptyset$ and if $X_{1}\subset I^{\prime}$ then $(I\cup X_{2}\cup
X_{3})\cap(D^{\prime}_{1}\cup D^{\prime}_{2}\cup D^{\prime}_{3})=\emptyset$, a
contradiction. Proceeding similarly for $X_{2},X_{3}$, we are in the case that
$X\cap I^{\prime}=\emptyset$ and thus $|(I\cup
X)\cap((C^{\prime}_{0}-C^{\prime}_{6})\cup(C^{\prime}_{6}-C^{\prime}_{0}))|\geq
b+1+6+b-2-a=4$. Hence, without lost of generality,
$(C^{\prime}_{0}-C^{\prime}_{6})\cup Z^{\prime}_{1}\subset I\cup X$, a
contradiction with $|D^{\prime}_{1}\cap D_{i}|\leq 1$. ∎

## References

  * [1] Y. Aubry, J.-C. Godin and O. Togni,  Every triangle-free induced subgraph of the triangular lattice is $(5m,2m)$-choosable,  Discrete Applied Math. 166, (2014), 51-58.
  * [2] D. W. Cranston, L. Rabern,  Planar graphs are 9/2-colorable,  Journal of Combinatorial Theory, Series B, 133, (2018), 32-45.
  * [3] J.-C. Godin,  Coloration et choisissabilité des graphes et applications,  PhD thesis (in french), Université du Sud Toulon-Var, France (2009).
  * [4] F. Havet,  Channel assignement and multicolouring of the induced subgraphs of the triangular lattice.  Discrete Math. 233, (2001), 219-233.
  * [5] J. Janssen, D. Krizanc, L. Narayanan and S. Shende,  Distributed Online Frequency Assignment in Cellular Networks Journal of Algorithms, Proceedings, 36(2) (2000), 119-151.
  * [6] C. McDiarmid and B. Reed.  Channel assignement and weighted coloring. Networks, 36, (2000), 114-117.
  * [7] L. Narayanan and S.M. Shende,  Static frequency assignement in cellular networks,  Algoritmica, 29, (2001), 396-409.
  * [8] I. Sau, P. Šparl and J. Žerovnik,  Simpler multicoloring of triangle-free hexagonal graphs,  Discrete Mathematics, 312(1), (2012), 181-187.
  * [9] P. Šparl, R. Witkowski, and J. Žerovnik,  1-local $\frac{7}{5}$-competitive algorithm for multicoloring hexagonal graphs,  Algorithmica 64, (2012), 564-583.
  * [10] P. Šparl, R. Witkowski, J. Žerovnik  Multicoloring of cannonball graphs Ars Math. Contemp. 10, (2016), 31–44.
  * [11] S. Stahl,  n-tuple colorings and associated graphs,  J. Comb. Theory (Ser. B) 20, (1976), 185-203.
  * [12] K.S. Sudeep and S. Vishwanathan.  A technique for multicoloring triangle-free hexagonal graphs,  Discrete Math. 300, (2005), 256-259.
  * [13] R. Witkowski, J. Žerovnik,  Proof of McDiarmid-Reed conjecture for a subclass of hexagonal graphs.  Utilitas Mathematica 105, (2017), 191–206.