# The achromatic number of $K_{6}\square K_{7}$ is $18$

Mirko Horňák
Institute of Mathematics, P.J. Šafárik University
Jesenná 5, 040 01 Košice, Slovakia E-mail address<EMAIL_ADDRESS>
###### Abstract

A vertex colouring $f:V(G)\to C$ of a graph $G$ is complete if for any two
distinct colours $c_{1},c_{2}\in C$ there is an edge $\\{v_{1},v_{2}\\}\in
E(G)$ such that $f(v_{i})=c_{i}$, $i=1,2$. The achromatic number of $G$ is the
maximum number $\mathrm{achr}(G)$ of colours in a proper complete vertex
colouring of $G$. In the paper it is proved that $\mathrm{achr}(K_{6}\square
K_{7})=18$. This result finalises the determination of
$\mathrm{achr}(K_{6}\square K_{q})$.

Keywords: complete vertex colouring, achromatic number, Cartesian product

##  1 Introduction

Consider a finite simple graph $G$ and a finite colour set $C$. A vertex
colouring $f:V(G)\to C$ is complete if for any two distinct colours
$c_{1},c_{2}\in C$ one can find an edge $\\{v_{1},v_{2}\\}\in E(G)$
($\\{v_{1},v_{2}\\}$ is usually shortened to $v_{1}v_{2}$). The achromatic
number of $G$, in symbols $\mathrm{achr}(G)$, is the maximum cardinality of
$C$ admitting a proper complete vertex colouring of $G$. The invariant was
introduced by Harary, Hedetniemi, and Prins in [4], where the following
interpolation theorem was proved:

######  Theorem 1.

If $G$ is a graph, and $\chi(G)\leq k\leq\mathrm{achr}(G)$ for an integer $k$,
there exists a $k$-element colour set $C$ and a proper complete vertex
colouring $f:V(G)\to C$. ∎

Let $G\square H$ denote the Cartesian product of graphs $G$ and $H$ (the
notation follows the monograph [10] by Imrich and Klavžar). So,
$V(K_{p}\square K_{q})=V(K_{p})\times V(K_{q})$, and $E(K_{p}\square K_{q})$
consists of all edges $(x,y_{1})(x,y_{2})$ with $y_{1}\neq y_{2}$ and all
edges $(x_{1},y)(x_{2},y)$ with $x_{1}\neq x_{2}$. The problem of determining
$\mathrm{achr}(K_{p}\square K_{q})$ is motivated by the fact that, according
to Chiang and Fu [2], $\mathrm{achr}(G\square H)\geq\mathrm{achr}(K_{p}\square
K_{q})$ for arbitrary graphs $G,H$ with $\mathrm{achr}(G)=p$ and
$\mathrm{achr}(H)=q$. Clearly, $\mathrm{achr}(K_{q}\square
K_{p})=\mathrm{achr}(K_{p}\square K_{q})$, so it is natural to suppose $p\leq
q$. The case $p\in\\{2,3,4\\}$ was solved by Horňák and Puntigán in [9], and
that of $p=5$ by Horňák and Pčola in [7, 8].

######  Proposition 2 (see [1]).

$\mathrm{achr}(K_{6}\square K_{6})=18$.

More generally, in [3] Chiang and Fu proved that if $r$ is an odd projective
plane order, then $\mathrm{achr}(K_{(r^{2}+r)/2}\square
K_{(r^{2}+r)/2})=(r^{3}+r^{2})/2$.

The aim of the present paper is to finalise the determination of $K_{6}\square
K_{q}$ (for $q\geq 8$ see Horňák [5, 6]) by proving

######  Theorem 3.

$\mathrm{achr}(K_{6}\square K_{7})=18$.

For $k,l\in\mathbb{Z}$ we denote integer intervals by

$[k,l]=\\{z\in\mathbb{Z}:k\leq z\leq
l\\},\qquad[k,\infty)=\\{z\in\mathbb{Z}:k\leq z\\}.$

Further, for a set $A$ and $m\in[0,\infty)$ let $\binom{A}{m}$ be the set of
$m$-element subsets of $A$.

If we suppose that $V(K_{r})=[1,r]$ for $r\in[1,\infty)$, then a vertex
colouring $f:V(K_{p}\square K_{q})\to C$ can be conveniently desribed using
the $p\times q$ matrix $M=M(f)$, in which the entry in the $i$th row and the
$j$th column is $(M)_{i,j}=f(i,j)$.

If $f$ is proper, then each line (row or column) of $M$ consists of pairwise
distinct entries.

If $f$ is complete, then each pair $\\{c_{1},c_{2}\\}\in\binom{C}{2}$ (of
colours in $C$) is good in $M$ in the sense that either there are $i\in[1,p]$
and $j_{1},j_{2}\in[1,q]$ such that
$\\{c_{1},c_{2}\\}=\\{(M)_{i,j_{1}},(M)_{i,j_{2}}\\}$, which is expressed by
saying that the pair $\\{c_{1},c_{2}\\}$ is row-based (in $M$) or there are
$i_{1},i_{2}\in[1,p]$ and $j\in[1,q]$ such that
$\\{c_{1},c_{2}\\}=\\{(M)_{i_{1},j},(M)_{i_{2},j}\\}$, i.e., the pair
$\\{c_{1},c_{2}\\}$ is column-based (in $M$). For $(i,j)\in[1,p]\times[1,q]$
and $C^{\prime}\subseteq C\setminus\\{(M)_{i,j}\\}$ let $g(i,j,C^{\prime})$
denote the number of pairs $\\{(M)_{i,j},\gamma\\}$ with $\gamma\in
C^{\prime}$ that are good in $M$, while this fact is documented by the
$(i,j)$-copy of the colour $(M)_{i,j}$.

Let $\mathcal{M}(p,q,C)$ be the set of $p\times q$ matrices $M$ with entries
from $C$ such that entries of any line of $M$ are pairwise distinct, and all
pairs in $\binom{C}{2}$ are good in $M$. Thus if $f:[1,p]\times[1,q]\to C$ is
a proper complete vertex colouring of $K_{p}\square K_{q}$, then
$M(f)\in\mathcal{M}(p,q,C)$.

Conversely, if $M\in\mathcal{M}(p,q,C)$, it is immediate to see that the
mapping $f_{M}:[1,p]\times[1,q]\to C$ determined by $f_{M}(i,j)=(M)_{i,j}$ is
a proper complete vertex colouring of $K_{p}\square K_{q}$.

So, we have just proved

######  Proposition 4.

If $p,q\in[1,\infty)$ and $C$ is a finite set, then the following statements
are equivalent:

$\mathrm{(}1)$ There is a proper complete vertex colouring of $K_{p}\square
K_{q}$ using as colours elements of $C$.

$\mathrm{(}2)$ $\mathcal{M}(p,q,C)\neq\emptyset$. ∎

The following straightforward proposition comes from [5].

######  Proposition 5.

If $p,q\in[1,\infty)$, $C,D$ are finite sets, $M\in\mathcal{M}(p,q,C)$,
mappings $\rho:[1,p]\to[1,p]$, $\sigma:[1,q]\to[1,q]$, $\pi:C\to D$ are
bijections, and $M_{\rho,\sigma}$, $M_{\pi}$ are $p\times q$ matrices defined
by $(M_{\rho,\sigma})_{i,j}=(M)_{\rho(i),\sigma(j)}$ and
$(M_{\pi})_{i,j}=\pi((M)_{i,j})$, then $M_{\rho,\sigma}\in\mathcal{M}(p,q,C)$
and $M_{\pi}\in\mathcal{M}(p,q,D)$. ∎

Let $M\in\mathcal{M}(p,q,C)$. The frequency of a colour $\gamma\in C$ is the
number of entries of $M$ equal to $\gamma$. An l-colour ($l+$colour) is a
colour of frequency $l$ (at least $l$), and $C_{l}$ ($C_{l+}$) is the set of
$l$-colours ($l+$colours). Further, for $k\in\\{l,l+\\}$ let $c_{k}=|C_{k}|$,

$\displaystyle\mathbb{R}(i)$ $\displaystyle=\\{(M)_{i,j}:j\in[1,q]\\},\ $
$\displaystyle\mathbb{R}_{k}(i)=C_{k}\cap\mathbb{R}(i),\ $ $\displaystyle
r_{k}(i)=|\mathbb{R}_{k}(i)|,\ $ $\displaystyle i\in[1,p],$
$\displaystyle\mathbb{C}(j)$ $\displaystyle=\\{(M)_{i,j}:i\in[1,p]\\},\ $
$\displaystyle\mathbb{C}_{k}(j)=C_{k}\cap\mathbb{C}(j),\ $ $\displaystyle
c_{k}(j)=|\mathbb{C}_{k}(j),\ $ $\displaystyle j\in[1,q].$

Finally, denote

$\displaystyle\mathbb{R}_{2}(i_{1},i_{2})$
$\displaystyle=C_{2}\cap\mathbb{R}(i_{1})\cap\mathbb{R}(i_{2}),\ $
$\displaystyle r_{2}(i_{1},i_{2})=|\mathbb{R}_{2}(i_{1},i_{2})|,\ $
$\displaystyle i_{1},i_{2}\in[1,p],i_{1}\neq i_{2},$
$\displaystyle\mathbb{C}_{2}(j_{1},j_{2})$
$\displaystyle=C_{2}\cap\mathbb{C}(j_{1})\cap\mathbb{C}(j_{2}),\ $
$\displaystyle c_{2}(j_{1},j_{2})=|\mathbb{C}_{2}(j_{1},j_{2})|,\ $
$\displaystyle j_{1},j_{2}\in[1,q],j_{1}\neq j_{2}.$

Considering a nonempty set $S\subseteq[1,p]\times[1,q]$ we say that a colour
$\gamma\in C$ occupies a position in $S$ (appears in $S$, has a copy in $S$ or
simply is in $S$) if there is $(i,j)\in S$ such that $(M)_{i,j}=\gamma$.

##  2 Properties of a counterexample to Theorem 3

We prove Theorem 3 by the way of contradiction. It is well known that
$\mathrm{achr}(G)\geq\mathrm{achr}(H)$ if $H$ is an induced subgraph of a
graph $G$. So, by Proposition 2, $\mathrm{achr}(K_{6}\square
K_{7})\geq\mathrm{achr}(K_{6}\square K_{6})=18$. Provided that Theorem 3 is
false, by Theorem 1 and Proposition 4 there is a set $C$ with $|C|=19$ and a
matrix $M\in\mathcal{M}(6,7,C)$; henceforth the whole notation corresponds to
this (hypothetical) matrix $M$.

For a colour $\gamma\in C$ denote
$V_{\gamma}=f_{M}^{-1}(\gamma)\subseteq[1,6]\times[1,7]$, and let
$N(V_{\gamma})$ be the neighbourhood of $V_{\gamma}$ (the union of
neighborhoods of vertices in $V_{\gamma}$). The excess of $\gamma$ is defined
to be the maximum number $\mathrm{exc}(\gamma)$ of vertices in a set
$S\subseteq N(V_{\gamma})$ such that the partial vertex colouring of
$K_{6}\square K_{7}$, obtained by removing colours of $S$, is complete
concerning the colour class $\gamma$.

######  Claim 1.

If $\gamma\in C_{l}$, then $\mathrm{exc}(\gamma)=-l^{2}+12l-18$.

Proof. The vertex colouring $f_{M}$ of $K_{6}\square K_{7}$ is proper, hence
$|N(V_{\gamma})|=7l+l(6-l)-l=l(12-l)$. Further, $f_{M}$ is complete, and so
each colour of $C\setminus\\{\gamma\\}$ occupies a position in
$N(V_{\gamma})$. As a consequence,
$\mathrm{exc}(\gamma)=l(12-l)-(19-1)=-l^{2}+12l-18$. $\blacksquare$

######  Claim 2.

The following statements are true:

$1.$ $c_{1}=0$;

$2.$ if $l\in[7,\infty)$, then $c_{l}=0$;

$3.$ $c_{2}\in[15,18]$;

$4.$ $c_{3+}\in[1,4]$;

$5.$ $c_{4+}\leq c_{2}-15$;

$6.$ if $c_{4+}=0$, then $c_{3+}=c_{3}=4$;

$7.$ if $c_{4+}\geq 1$, then $c_{3+}\leq 3$;

$8.$ $c_{3+}+c_{4+}\leq 4$;

$9.$ if $c_{5+}\geq 1$, then $c_{3+}+c_{4+}\leq 3$;

$10.$ $\Sigma=\sum_{i=3}^{6}ic_{i}\in[6,12]$;

$11.$ if $i_{1},i_{2}\in[1,6]$, $i_{1}\neq i_{2}$, then
$r_{2}(i_{1},i_{2})\leq 3$.

Proof. 1\. If $\gamma\in C_{1}$, then, by Claim 1,
$\mathrm{exc}(\gamma)=-7<0$, a contradiction.

2\. If $\gamma\in C_{l}$ for some $l\in[7,\infty)$, by the pigeonhole
principle the colouring $f_{M}$ is not proper, a contradiction.

3\. By Claims 2.1, 2.2 we have $c_{2}+c_{3+}=\sum_{i=2}^{6}c_{i}=|C|=19$ and
$\sum_{i=2}^{6}ic_{i}=|V(K_{6}\square K_{7})|=42$, hence
$2c_{2}+6(19-c_{2})=2c_{2}+6c_{3+}\geq\sum_{i=2}^{6}ic_{i}\geq
2c_{2}+3c_{3+}=2c_{2}+3(19-c_{2})$, which yields $114-4c_{2}\geq 42\geq
57-c_{2}$ and $15\leq c_{2}\leq 18$.

4\. A consequence of Claim 2.3.

5\. We have $3\cdot
19-c_{2}+c_{4+}=3(c_{2}+c_{3}+c_{4+})-c_{2}+c_{4+}\leq\sum_{i=2}^{6}ic_{i}=42$
and $c_{4+}\leq c_{2}-15$.

6\. If $c_{4+}=0$, then $c_{2}+c_{3}=19$, $2c_{2}+3c_{3}=42$ and
$c_{3+}=c_{3}=42-2\cdot 19=4$.

7\. The assumption $c_{4+}\geq 1$ and $c_{3+}=4$ would mean $\Sigma\geq 3\cdot
3+4=13>12$, a contradiction.

8\. If $c_{4+}=0$, then $c_{3+}+c_{4+}=c_{3+}\leq 4$. With $c_{4+}=1$ we have,
by Claim 2.5, $1=c_{4+}\leq c_{2}-15$, $c_{2}\geq 16$,
$c_{3}=19-c_{2}-c_{4+}\leq 2$, $c_{3+}\leq 3$ and $c_{3+}+c_{4+}\leq 4$.
Finally, from $c_{4+}\geq 2$ it follows that $2\leq c_{4+}\leq c_{2}-15$,
$c_{2}\geq 17$, $19=c_{2}+c_{3}+c_{4+}\geq 17+c_{3}+2=19+c_{3}\geq 19$,
$c_{2}=17$, $c_{3}=0$, $c_{4+}=2=c_{3+}$ and $c_{3+}+c_{4+}=4$.

9\. We have
$2(19-c_{5+})+5c_{5+}=2(c_{2}+c_{3}+c_{4})+5(c_{5}+c_{6})\leq\sum_{i=2}^{6}ic_{i}=42$,
$3c_{5+}\leq 4$ and $c_{3}+2c_{4}=42-2(19-c_{5}-c_{6})-5c_{5}-6c_{6}\leq
4-3c_{5+}$, hence $c_{5+}\geq 1$ yields $c_{5+}=1$, $c_{3}+2c_{4}\leq 1$ and
$c_{3+}+c_{4+}\leq 1+2=3$.

10\. The assertion of Claim 2.3 leads to
$\sum_{i=3}^{6}ic_{i}=\sum_{i=2}^{6}ic_{i}-2c_{2}=42-2c_{2}\in[6,12]$.

11\. The inequality is trivial if $r_{2}(i_{1},i_{2})=0$. If
$\gamma\in\mathbb{R}_{2}(i_{1},i_{2})$, then each colour of
$\mathbb{R}_{2}(i_{1},i_{2})\setminus\\{\gamma\\}$ contributes one to the
excess of $\gamma$, hence, by Claim 1,
$r_{2}(i_{1},i_{2})-1\leq\mathrm{exc}(\gamma)=2$ and $r_{2}(i_{1},i_{2})\leq
3$. $\blacksquare$

A set $D\subseteq C_{2}$ is of the type $(m_{1}^{a_{1}}\negthinspace\dots
m_{k}^{a_{k}},n_{1}^{b_{1}}\negthinspace\dots n_{l}^{b_{l}})$ if
$(m_{1},\dots,m_{k})$, $(n_{1},\dots,n_{l})$ are decreasing sequences of
integers from the interval $[1,|D|]$,
$|\\{i\in[1,6]:|D\cap\mathbb{R}(i)|=m_{i}\\}|=a_{i}\geq 1$ for each
$i\in[1,k]$, and $|\\{j\in[1,7]:|D\cap\mathbb{C}(j)|=n_{j}\\}|=b_{j}\geq 1$
for each $j\in[1,l]$; clearly,
$\sum_{i=1}^{k}m_{i}a_{i}=2|D|=\sum_{j=1}^{l}n_{j}b_{j}$.

Forthcoming Claims 3, 6, 4, 7, and 9 state that certain types of 2- and
3-element subsets of $C_{2}$ are impossible in a matrix $M$ contradicting
Theorem 3. The mentioned claims are proved by contradiction. When proving that
$M$ avoids a type $T$, we suppose that there is $D\subseteq C_{2}$, which is
of the type $T$ (without explicitly mentioning it), and we reach a
contradiction with some of the properties following from the fact that
$M\in\mathcal{M}(6,7,C)$.

######  Claim 3.

No set $\\{\alpha,\beta\\}\subseteq C_{2}$ is of the type $(1^{4},2^{2})$.

Proof. Since we have at our disposal Proposition 5, we may suppose without
loss of generality that $(M)_{1,1}=\alpha=(M)_{3,2}$ and
$(M)_{2,1}=\beta=(M)_{4,2}$. We use (w) to express briefly that it is
Proposition 5, which enables us to simplify our reasoning by restricting our
attention to matrices with a special structure. With
$A=\mathbb{C}(1)\cup\mathbb{C}(2)$ we have $|A|\leq 10$. If $\gamma\in
C\setminus A$, the fact that both pairs $\\{\gamma,\alpha\\}$ and
$\\{\gamma,\beta\\}$ are good forces $\gamma$ to occupy a position in
$S_{\alpha}=\\{1,3\\}\times[3,7]$ and in $S_{\beta}=\\{2,4\\}\times[3,7]$ as
well. So, $|C\setminus A|\leq 10$ and $|C\setminus A|=|C|-|A|\geq 9$. By Claim
2.4, $|(C\setminus A)\cap C_{2}|=|C\setminus A|-|(C\setminus A)\cap
C_{3+}|\geq 9-c_{3+}\geq 5$, hence there is $(i,k)\in\\{1,3\\}\times\\{2,4\\}$
such that $\delta\in\mathbb{R}_{2}(i,k)\cap(C\setminus A)$. If $(i,k)=(1,2)$,
(w) $(M)_{1,3}=\delta=(M)_{2,4}$.

If $|C\setminus A|=10$, then all ten positions in both $S_{\alpha}$,
$S_{\beta}$ are occupied by colours of $C\setminus A$, and all twelve bullet
positions in Fig. 1 are occupied by colours of $(C\setminus
A)\setminus\\{\delta\\}$, which means that $\mathrm{exc}(\delta)\geq
12-|(C\setminus A)\setminus\\{\delta\\}|=12-(10-1)=3$ in contradiction to
Claim 1.

If $|C\setminus A|=9$, then
$\mathbb{C}(1)\cap\mathbb{C}(2)=\\{\alpha,\beta\\}$. Let $B$ be the set of
four colours occupying a position in $[5,6]\times[1,2]$. Using
$\mathrm{exc}(\alpha)=\mathrm{exc}(\beta)=2$ we see that exactly two positions
in $[1,4]\times[3,7]$ are occupied by a colour of $B$. Thus, if
$\varepsilon\in B$ is not in $[1,4]\times[3,7]$, it must be in
$[5,6]\times[3,7]$, and so $\varepsilon\in C_{2}$. Then, however, the number
of pairs $\\{\zeta,\varepsilon\\}$ with $\zeta\in(C\setminus A)\cap C_{2}$
that are good is at most four, while $|(C\setminus A)\cap
C_{2}|\geq|C\setminus A|-|C_{3+}|\geq 9-4=5$, a contradiction.

Provided that $(i,k)\neq(1,2)$, a contradiction can be reached in a similar
manner. $\blacksquare$

$\begin{pmatrix}\alpha&.&\delta&\bullet&\bullet&\bullet&\bullet\\\
\beta&.&\bullet&\delta&\bullet&\bullet&\bullet\\\
.&\alpha&\bullet&\bullet&.&.&.\\\ .&\beta&\bullet&\bullet&.&.&.\\\
.&.&.&.&.&.&.\\\ .&.&.&.&.&.&.\\\
\end{pmatrix}\begin{pmatrix}\alpha&\beta&.&.&.&.&.\\\
.&.&\alpha&\beta&.&.&.\\\ \gamma&\bullet&\bullet&\bullet&.&.&.\\\
\bullet&\gamma&\bullet&\bullet&.&.&.\\\ \bullet&\bullet&.&.&.&.&.\\\
\bullet&\bullet&.&.&.&.&.\end{pmatrix}\begin{pmatrix}\alpha&\beta&.&.&\circ&.&.\\\
\zeta/.&./\zeta&\alpha&\beta&\circ&\circ&\circ\\\
\gamma&.&.&.&.&\bullet&\bullet\\\ .&\gamma&.&.&.&\bullet&\bullet\\\
.&.&.&.&\zeta&.&.\\\ .&.&.&.&.&.&.\end{pmatrix}$ $\hskip
1.42262pt\mathrm{Fig.\ 1}\hskip 99.58464pt\mathrm{Fig.\ 2}\hskip
99.58464pt\mathrm{Fig.\ 3}\ $

######  Claim 4.

No set $\\{\alpha,\beta\\}\subseteq C_{2}$ is of the type
$(2^{1}1^{2},2^{2})$.

Proof. Now (w) $(M)_{1,1}=\alpha=(M)_{2,2}$ and $(M)_{2,1}=\beta=(M)_{3,2}$.
With $A=\mathbb{C}(1)\cup\mathbb{C}(2)\cup\mathbb{R}(2)$ each colour
$\gamma\in C\setminus A$ has a copy in $\\{i\\}\times[3,7]$, $i=1,3$
($\\{\gamma,\alpha\\}$ and $\\{\gamma,\beta\\}$ are good). From $|A|\leq 15$
it follows that $|C\setminus A|\geq 19-15=4$, and then $C\setminus A\subseteq
C_{3+}$: indeed, if $\delta\in(C\setminus A)\cap C_{2}$, then
$\mathrm{exc}(\delta)\geq|(C\setminus A)\setminus\\{\delta\\}|\geq 3$, a
contradiction. Thus $C_{2}\subseteq A$, $c_{2}\leq 15$, hence, by Claims 2.3,
2.4, $c_{2}=15$, $c_{3}=c_{3+}=4$, $C\setminus A=C_{3+}=C_{3}$, each colour of
$C_{2}\setminus\\{\alpha,\beta\\}$ has exactly one copy in
$([1,6]\times[1,2])\cup(\\{2\\}\times[3,7])$, and (w) $\varepsilon=(M)_{1,2}$,
$\zeta=(M)_{3,1}$ are (distinct) 2-colours.

First note that $\varepsilon,\zeta\notin\mathbb{R}_{2}(1,3)$, for otherwise
$\max(\mathrm{exc}(\varepsilon),\mathrm{exc}(\zeta))\geq c_{3}=4$. So, the
second copies of $\varepsilon,\zeta$ are in $[4,6]\times[3,7]$, and the pair
$\\{\varepsilon,\zeta\\}$ is good in the corresponding $3\times 5$ submatrix
of $M$.

If the pair $\\{\varepsilon,\zeta\\}$ is column-based, (w)
$\varepsilon=(M)_{4,3}$ and $\zeta=(M)_{5,3}$, then, with a (2-) colour $\eta$
appearing in $\\{2\\}\times[4,7]$, both pairs $\\{\eta,\varepsilon\\}$ and
$\\{\eta,\zeta\\}$ are good only if $\eta$ occupies a position in
$\\{1,3,6\\}\times\\{3\\}$, a contradiction.

If the pair $\\{\varepsilon,\zeta\\}$ is row-based, (w)
$\varepsilon=(M)_{4,3}$ and $\zeta=(M)_{4,4}$, consider six positions in
$[5,6]\times[5,7]$. Since $r_{3}(1)=r_{3}(3)=4=c_{3}$, at most four of those
positions are occupied by 3-colours and at least two of them by 2-colours. Let
$B$ be the set of 2-colours having a copy in
$([5,6]\times[5,7])\cup(\\{2\\}\times[5,7])$. If $\vartheta\in B$, then,
having in mind that both pairs $\\{\vartheta,\varepsilon\\}$ and
$\\{\vartheta,\zeta\\}$ are good, $\vartheta$ must have a copy in
$\\{(1,4),(3,3),(4,1),(4,2)\\}$; this yields a contradiction, because $|B|\geq
5$. $\blacksquare$

######  Claim 5.

If $j,l\in[1,7]$, $j\neq l$, then $c(j,l)\leq 2$.

Proof. The assumption $c(j,l)\geq 3$ would contradict Claim 3 or Claim 4.
$\blacksquare$

######  Claim 6.

No set $\\{\alpha,\beta\\}\subseteq C_{2}$ is of the type $(2^{2},1^{4})$.

Proof. Here (w) $(M)_{1,1}=\alpha=(M)_{2,3}$ and $(M)_{1,2}=\beta=(M)_{2,4}$.
With $A=\mathbb{R}(1)\cup\mathbb{R}(2)$ we have $|A|\leq 12$, each colour of
$C\setminus A$ is in both sets $S_{\alpha}=[3,6]\times\\{1,3\\}$,
$S_{\beta}=[3,6]\times\\{2,4\\}$, and $7\leq|C\setminus A|\leq 8$. As
$|(C\setminus A)\cap C_{2}|\geq 3$, there is
$(j,l)\in\\{1,3\\}\times\\{2,4\\}$ such that $\gamma\in(C\setminus
A)\cap\mathbb{C}_{2}(j,l)$.

If $(j,l)=(1,2)$, (w) $(M)_{3,1}=\gamma=(M)_{4,2}$.

If $|C\setminus A|=8$, all eight positions in both sets $S_{\alpha}$,
$S_{\beta}$ are occupied by colours of $C\setminus A$. Further, all ten bullet
positions in Fig. 2, which are positions of vertices in $(N(V_{\alpha})\cup
N(V_{\beta}))\cap N(V_{\gamma})$, are occupied by colours of $(C\setminus
A)\setminus\\{\gamma\\})$, and so $\mathrm{exc}(\gamma)\geq 10-(8-1)=3$, a
contradiction.

Suppose that $|C\setminus A|=7$ (and $A|=12$). For $m\in\\{2,3+,4+\\}$ and
$n\in[0,2]$ let $C_{m}^{n}$ be the set of colours in $C_{m}$ having $n$ copies
in $[5,6]\times[5,7]$, and let $c_{m}^{n}=|C_{m}^{n}|$. If $\delta\in
C_{2}^{1}\cup C_{3}^{2}$, then, since the pairs $\\{\delta,\alpha\\}$,
$\\{\delta,\beta\\}$ and $\\{\delta,\gamma\\}$ are good, $\delta$ must appear
in $\\{2\\}\times[1,2]$, and so $c_{2}^{1}+c_{3}^{2}\leq 2$; further,
$c_{2}^{2}=0$. Using Claim 2.8 we obtain

$\displaystyle 6$
$\displaystyle=c_{2}^{1}+c_{3}^{1}+c_{4+}^{1}+2c_{3}^{2}+2c_{4+}^{2}\leq
c_{2}^{1}+c_{3}^{2}+\sum_{n=0}^{2}(c_{3}^{n}+c_{4+}^{n})+c_{4+}^{2}$
$\displaystyle\leq c_{2}^{1}+c_{3}^{2}+c_{3+}+c_{4+}\leq 2+4=6,$ (1)

which implies

$\displaystyle c_{3}^{0}=c_{4+}^{0}=c_{4+}^{1}$ $\displaystyle=0,$ (2)
$\displaystyle c_{4+}$ $\displaystyle=c_{4+}^{2},$ (3) $\displaystyle
c_{2}^{1}+c_{3}^{2}$ $\displaystyle=2,$ (4)

$c_{3+}+c_{4+}=4$, and so, by Claim 2.9, $c_{5+}=0$.

For $\delta\in\\{\alpha,\beta\\}$ choose a set $S_{\delta^{\prime}}\subseteq
S_{\delta}$ with $|S_{\delta^{\prime}}|=7$ occupied by seven distinct colours
of $C\setminus A$, and let
$P=([3,6]\times[1,4])\setminus(S_{\alpha^{\prime}}\cup S_{\beta^{\prime}})$;
then $|P|=2$. Since $|N(V_{\gamma})\cap([3,6]\times[1,4])|=10$, we have
$2=\mathrm{exc}(\gamma)\geq 10-(|P|+|(C\setminus
A)\setminus\\{\gamma\\}|=4-|P|=2$, hence both positions in $P$ are necessarily
occupied by a colour of $A$, and all sets
$S_{\alpha^{\prime}},S_{\beta^{\prime}},P$ are unique. We express this
property of $\gamma$ by saying that $\gamma$ is $A$-exact. Besides that, the
two positions in $P$ are occupied by two distinct colours of $A$, say
$\lambda$ and $\mu$; indeed, otherwise the colour of $A$, which occupies both
positions in $P$, by (3), would be a 5+colour, a contradiction. Let
$P=\\{(i_{\lambda},j_{\lambda}),(i_{\mu},j_{\mu})\\}$, where
$\lambda=(M)_{i_{\lambda},j_{\lambda}}$ and $\mu=(M)_{i_{\mu},j_{\mu}}$. The
excess of both $\alpha,\beta$ is 2, therefore
$(j_{\lambda},j_{\mu})\in\\{1,3\\}\times\\{2,4\\}$ (a colour occupying a
position in $P$ contributes to the excess of either $\alpha$ or $\beta$, and
$\alpha,\beta$ are contributing to the excess of each other).

The above reasoning concerning $\gamma$ can be repeated to prove that any
colour in $(C\setminus A)\cap C_{2}$ is $A$-exact.

Suppose that $\varepsilon\in(C\setminus A)\cap C_{2}$; then $\varepsilon$ is
$A$-exact and $\varepsilon\in\mathbb{C}_{2}(j^{\prime},l^{\prime})$, where
$(j^{\prime},l^{\prime})\in\\{1,3\\}\times\\{2,4\\}$. Let
$\\{l_{\lambda},l_{\mu}\\}=[1,4]\setminus\\{j_{\lambda},j_{\mu}\\}$.

Assume first that $i_{\lambda}=i_{\mu}$. By Claim 4, $|(C\setminus
A)\cap\mathbb{C}_{2}(j_{\lambda},j_{\mu})|\leq 2$. If
$(j^{\prime},l^{\prime})\neq(j_{\lambda},j_{\mu})$, then either
$\varepsilon=(M)_{i_{\lambda},l_{\lambda}}$ or
$\varepsilon=(M)_{i_{\lambda},l_{\mu}}$.

The second possibility is $i_{\lambda}\neq i_{\mu}$. By Claim 4, $|(C\setminus
A)\cap\mathbb{C}_{2}(l_{\lambda},l_{\mu})|\leq 2$. On the other hand, if
$(j^{\prime},l^{\prime})\neq(l_{\lambda},l_{\mu})$, then either
$\varepsilon=(M)_{i_{\lambda},j_{\mu}}$ or
$\varepsilon=(M)_{i_{\mu},j_{\lambda}}$.

In both cases $|(C\setminus A)\cap C_{2}|\leq 2+2=4$ and

$|(C\setminus A)\cap C_{3+}|\geq 7-4=3.$ (5)

From (2) and (3) we obtain $(C\setminus A)\cap C_{3+}\subseteq C_{3}^{1}\cup
C_{4+}^{2}$, hence $c_{3}^{1}+c_{4+}^{2}\geq 3$. Let us show the following:

(*) No 3+colour occupies a position in $[3,4]\times[5,7]$, and $c_{2}^{1}\geq
1$.

Because of (2) and (3) we know that colours of $(C\setminus A)\cap C_{3+}$
appear only in $([3,6]\times[1,4])\cup([5,6]\times[5,7])$. If $c_{4+}\geq 1$,
then, by Claim 2.7, $3\geq c_{3+}\geq c_{3}^{1}+c_{4+}^{2}\geq 3$,
$c_{3+}=c_{3}^{1}+c_{4+}^{2}=3$, $C_{3+}=C_{3}^{1}\cup C_{4+}^{2}=(C\setminus
A)\cap C_{3+}$, $c_{3}^{2}=0$, $c_{2}^{1}=2$ (see (4)), and so (*) is true.

If $c_{4+}=0$, from (2), (4) and Claim 2.4 it follows that
$c_{3}^{1}+c_{3}^{2}=4=c_{3+}$, $C_{3+}=C_{3}^{1}\cup C_{3}^{2}=((C\setminus
A)\cap C_{3+})\cup C_{3}^{2}$ and, by (5), $c_{3}^{1}\geq 3$; since a colour
of $C_{3}^{2}$ is only in $(\\{2\\}\times[1,2])\cup([5,6]\times[5,7])$,
$c_{3}^{2}\leq 1$ and $c_{2}^{1}\geq 1$, (*) is true again.

Now, by (*), six positions in $[3,4]\times[5,7]$ are occupied by six distinct
2-colours belonging to $A\setminus\\{\lambda,\mu\\}$, and there is a colour
$\zeta\in C_{2}^{1}$, (w) $\zeta=(M)_{5,5}$, see Fig. 3. If a 2-colour $\eta$
appears in a bullet position, then, since the pair $\\{\eta,\zeta\\}$ is good,
the second copy of $\eta$ must occupy a circle position. In such a case,
however, it is easy to check that there is a set
$\\{\vartheta,\iota\\}\subseteq A\cap C_{2}$ of 2-colours occupying two bullet
positions and two circle positions, which contradicts either Claim 3 or Claim
4.

The case $(j,l)\neq(1,2)$ can be treated similarly. $\blacksquare$

######  Claim 7.

No set $\\{\alpha,\beta\\}\subseteq C_{2}$ is of the type
$(2^{2},2^{1}1^{2})$.

Proof. Let (w) $(M)_{1,1}=\alpha=(M)_{2,2}$ and $(M)_{1,2}=\beta=(M)_{2,3}$.
First of all, we have $\mathbb{R}_{2}(1,2)=\\{\alpha,\beta\\}$. Indeed, if (w)
$\gamma\in\mathbb{R}(1,2)\setminus\\{\alpha,\beta\\}$, then, by Claim 6,
necessarily $(M)_{1,3}=\gamma=(M)_{2,1}$. Each colour $\delta\in
C\setminus\mathbb{R}_{2}(1,2)$ occupies at least two positions in
$[3,6]\times[1,3]$ (all pairs $\\{\delta,\alpha\\}$, $\\{\delta,\beta\\}$,
$\\{\delta,\gamma\\}$ are good), hence $|C|\leq 11+\lfloor\frac{4\cdot
3}{2}\rfloor=17<19$, a contradiction.

With $A=\mathbb{R}(1)\cup\mathbb{R}(2)\cup\mathbb{C}(2)$ any colour $\gamma\in
C\setminus A$ occupies a position in $[3,6]\times\\{1\\}$ as well as in
$[3,6]\times\\{3\\}$, hence $|C\setminus A|\leq 4$, $|A|\leq 16$, $|C\setminus
A|=19-|A|\geq 3$ and $|A|\geq 15$.

Assume first that $|A|=15$ and $|C\setminus A|=4$, which yields $C\setminus
A\subseteq C_{3+}$ (a 2-colour $\gamma\in C\setminus A$ would satisfy
$\mathrm{exc}(\gamma)\geq 3$), $c_{3+}=c_{3}=4$ and $A=C_{2}$. For colours
$\gamma=(M)_{1,3}$ and $\delta=(M)_{2,1}$ their second copies appear in
$[3,6]\times(\\{2\\}\cup[4,7])$, and the pair $\\{\gamma,\delta\\}$ is good in
the corresponding $4\times 5$ submatrix of $M$. However, at most one of
$\gamma,\delta$ is in $[3,6]\times\\{2\\}$, hence $\\{\gamma,\delta\\}$ is
good in the submatrix of $M$ corresponding to $[3,6]\times[4,7]$.

If the pair $\\{\gamma,\delta\\}$ is column-based, (w) $\gamma=(M)_{3,4}$ and
$\delta=(M)_{4,4}$, at most one of colours in $[5,6]\times\\{2\\}$ belongs to
$\mathbb{R}(1)\cup\mathbb{R}(2)$, hence there is a 2-colour $\varepsilon$ and
$i\in[5,6]$ such that $\varepsilon=(M)_{i,2}=(M)_{11-i,4}$ (so that both pairs
$\\{\varepsilon,\gamma\\}$, $\\{\varepsilon,\delta\\}$ are good). For every
colour $\zeta\notin(\mathbb{C}(2)\cup\\{(M)_{i,4}\\}$ occupying a position in
$[1,2]\times[5,7]$ (the number of such colours is at least 4) there is
$\eta\in\\{\gamma,\delta,\varepsilon\\}$ such that the pair $\\{\eta,\zeta\\}$
is not good, a contradiction.

If the pair $\\{\gamma,\delta\\}$ is row-based, (w) $\gamma=(M)_{3,4}$ and
$\delta=(M)_{3,5}$. If a colour $\varepsilon$ occupies a position in
$[4,6]\times\\{2\\}$ and does not belong to $\mathbb{R}(1)\cup\mathbb{R}(2)$
(there are at least two such colours), it must appear in $\\{3\\}\times[6,7]$
(pairs $\\{\varepsilon,\gamma\\}$ and $\\{\varepsilon,\delta\\}$ are good),
(w) $(M)_{4,2}=\varepsilon=(M)_{3,6}$ and $(M)_{5,2}=\zeta=(M)_{3,7}$. If a
2-colour $\eta$ is in $\\{6\\}\times[4,7]$, then $\eta=(M)_{3,2}$ (all pairs
$\\{\eta,\vartheta\\}$ with
$\vartheta\in\\{\gamma,\delta,\varepsilon,\zeta\\}$ are good), $r_{3}(6)\geq
2+3=5>c_{3}$, and so the colouring $f_{M}$ is not proper, a contradiction.

From now on $|A|=16$ and $|C\setminus A|=3$. Suppose first that $C\setminus
A\subseteq C_{3+}$. From $c_{3+}\leq 4$ we obtain $|A\cap C_{3+}|\leq 1$.

If $(\mathbb{R}(1)\cup\mathbb{R}(2))\cap C_{3+}=\emptyset$, (w)
$\gamma=(M)_{3,2}$, $\delta=(M)_{4,2}$, $\varepsilon=(M)_{5,2}$ are 2-colours,
and their second copies appear in $[3,6]\times[4,7]$. Let
$J=\\{j\in[4,7]:\mathbb{C}(j)\cap\\{\gamma,\delta,\varepsilon\\}\neq\emptyset\\}$;
by Claim 5 we know that $2\leq|J|\leq 3$. If $(i,j)\in
S=\\{(1,3),(2,1)\\}\cup([1,2]\times([4,7]\setminus J))$, then
$g(i,j,\\{\gamma,\delta,\varepsilon\\})=0$; note that $|S|=10-2|J|$. On the
other hand, it is easy to see that the number of pairs
$(i,j)\in[3,6]\times[4,7]$, satisfying
$g(i,j,\\{\gamma,\delta,\varepsilon\\})=3$, is less than $|S|$ (at most 3 if
$|J|=3$ and at most 4 if $|J|=2$). Thus, there is a 2-colour $\zeta$ in $S$
and $\eta\in\\{\gamma,\delta,\varepsilon\\}$ such that the pair
$\\{\zeta,\eta\\}$ is not good.

If $|(\mathbb{R}(1)\cup\mathbb{R}(2))\cap C_{3+}|=1$, then $c_{3}=c_{3+}=4$
and $c_{2}(2)=6$.

Suppose first that both $\gamma=(M)_{1,3}$ and $\delta=(M)_{2,1}$ are
2-colours. The second copies of $\gamma,\delta$ are then in
$[3,6]\times[4,7]$, for if not,
$\max(\mathrm{exc}(\gamma),\mathrm{exc}(\delta))\geq 1+|C\setminus A|=4$.

If the pair $\\{\gamma,\delta\\}$ is column-based, (w) $\gamma=(M)_{3,4}$ and
$\delta=(M)_{4,4}$, then $(M)_{5,2}=\varepsilon=(M)_{6,4}$ and
$(M)_{6,2}=\zeta=(M)_{5,4}$ (all pairs
$\\{\varepsilon,\gamma\\},\\{\varepsilon,\delta\\},\\{\zeta,\gamma\\},$
$\\{\zeta,\delta\\}$ are good). For $(i,j)\in[1,2]\times[5,7]$ then
$g(i,j,\\{\gamma,\delta,\varepsilon,\zeta\\})=1$, and at least three positions
in $[1,2]\times[5,7]$ are occupied by a 2-colour that is in
$[3,6]\times[5,7]$; on the other hand, for $(i,j)\in[3,6]\times[5,7]$ we have
$g(i,j,\\{\gamma,\delta,\varepsilon,\zeta\\})\leq 2$, a contradiction.

If the pair $\\{\gamma,\delta\\}$ is row-based, (w) $\gamma=(M)_{3,4}$ and
$\delta=(M)_{3,5}$. Then $g(i,j,\\{\gamma,\delta\\})=0$ for
$(i,j)\in[4,6]\times\\{2\\}$ and $g(i,j,\\{\gamma,\delta\\})\leq 1$ for
$(i,j)\in[4,6]\times[4,7]$; this leads to a contradiction, since at least one
of colours in $[4,6]\times\\{2\\}$ has its second copy in $[4,6]\times[4,7]$.

So, one of $\gamma,\delta$ is a 2-colour and the other a 3-colour, (w)
$\gamma\in C_{2}$ and $\delta\in C_{3}$. As above, the second copy of $\gamma$
appears in $[3,6]\times[4,7]$, (w) $\gamma=(M)_{3,4}$. All colours of the set
$B=\\{\varepsilon,\zeta,\eta,\vartheta\\}$, where $\varepsilon=(M)_{3,2}$,
$\zeta=(M)_{4,2}$, $\eta=(M)_{5,2}$ and $\vartheta=(M)_{6,2}$, are 2-colours.
By Claim 3, the second copy of a colour $\iota\in B$ does not appear in
$\mathbb{C}(1)\cup\mathbb{C}(3)$, hence is in $[3,6]\times[4,7]$ and,
additionally, in $\mathbb{R}(3)\cup\mathbb{C}(4)$, provided that
$\iota\neq\varepsilon$ (the pair $\\{\iota,\gamma\\}$ is good). Clearly,
$|B\cap\mathbb{R}(3)|\leq 3$, since otherwise $\mathrm{exc}(\varepsilon)\geq
3$. So, by Claim 5, with $B^{\prime}=\\{\zeta,\eta,\vartheta\\}$ we have
$1\leq|B^{\prime}\cap\mathbb{C}(4)|\leq 2$.

If $|B^{\prime}\cap\mathbb{C}(4)|=2$, (w) $\eta=(M)_{4,4}$, $\zeta=(M)_{4,5}$
(here we use Claim 4) and $\vartheta=(M)_{3,5}$. For both $l\in[6,7]$ then
$g(2,l,B^{\prime}\cup\\{\gamma\\})=0$. This leads to a contradiction, since
$(M)_{2,6},(M)_{2,7}$ are 2-colours, and $g(i,j,B^{\prime}\cup\\{\gamma\\})=4$
only if $(i,j)=(6,4)$.

If $|B^{\prime}\cap\mathbb{C}(4)|=1$, (w) $\zeta=(M)_{5,4},\eta=(M)_{3,5}$ and
$\vartheta=(M)_{3,6}$, then $g(2,7,B^{\prime}\cup\\{\gamma\\})=0$. A
contradiction follows from the fact that
$g(i,j,B^{\prime}\cup\\{\gamma\\})\leq 3$ for each $(i,j)$.

Now suppose that $(C\setminus A)\cap C_{2}\neq\emptyset$, (w)
$\gamma=(M)_{3,1}=(M)_{4,3}\in(C\setminus A)\cap C_{2}$. For
$m\in\\{2,3,3+\\}$, $n\in[1,2]$ let $C_{m}^{n}$ be the set of colours in
$C_{m}$ having $n$ copies in $[5,6]\times[4,7]$ and $c_{m}^{n}=|C_{m}^{n}|$;
then

$c_{2}^{1}+c_{3+}^{1}+2c_{3+}^{2}=8.$ (6)

Since $g(i,j,\\{\alpha,\beta,\gamma\\})=0$ for $(i,j)\in[5,6]\times[4,7]$ and
$g(i,j,\\{\alpha,\beta,\gamma\\})=3$ if and only if $(i,j)\in
S=\\{(1,3),(2,1),(3,2),(4,2)\\}$, we have

$c_{2}^{1}+c_{3}^{2}\leq 4.$ (7)

Let us first show that $c_{2}^{1}\leq 3$. Indeed, if $c_{2}^{1}=4$, it is easy
to see that all pairs $\\{\delta,\varepsilon\\}\in\binom{C_{2}^{1}}{2}$ are
good only if there is $i\in[5,6]$ such that $C_{2}^{1}\subseteq\mathbb{R}(i)$.
This immediately implies $c_{3+}^{2}=0$ and, by Claim 2.4 and (6), $4\geq
c_{3+}\geq c_{3+}^{1}=4$, $c_{3+}=4$ and $C_{3+}\subseteq\mathbb{R}(11-i)$.
Then $\delta=(M)_{11-i,2}\in C_{2}$, the second copy of $\delta$ is in
$[3,4]\times[4,7]$ (by Claim 3), hence at least one of pairs
$\\{\delta,\varepsilon\\}$ with $\varepsilon\in C_{2}^{1}$ is not good, a
contradiction.

Further, we prove that

$c_{3+}^{1}+c_{3+}^{2}=c_{3+},$ (8)

which is equivalent to

$C_{3+}^{1}\cup C_{3+}^{2}=C_{3+}.$ (9)

If $c_{4+}\geq 1$, Claim 2.7 yields $c_{3+}\leq 3$. Because of (6) we obtain
$2(c_{3+}^{1}+c_{3+}^{2})=8+c_{3+}^{1}-c_{2}^{1}$,
$c_{3+}^{1}+c_{3+}^{2}=\frac{1}{2}(8+c_{3+}^{1}-c_{2}^{1})\geq\frac{1}{2}(8-3)=\frac{5}{2}$,
$3\geq c_{3+}\geq c_{3+}^{1}+c_{3+}^{2}\geq 3$, and so (24) is true under the
assumption $c_{4+}\geq 1$ (implying $c_{3+}=3$).

On the other hand, $c_{4+}=0$ implies $c_{3+}=c_{3}=4$ (Claim 2.6). In this
case, using (6) and (7), we see that
$8=(c_{2}^{1}+c_{3+}^{2})+(c_{3+}^{1}+c_{3+}^{2})\leq 4+c_{3+}=8$, hence
$c_{3+}=4=c_{2}^{1}+c_{3+}^{2}=c_{3+}^{1}+c_{3+}^{2}$, and (24) holds again.

Note that now necessarily $|(C\setminus A)\cap C_{2}|=1$. Indeed,
$|(C\setminus A)\cap C_{2}|=3$ is impossible by Claim 5, since in such a case
$c_{2}(1,3)\geq|(C\setminus A)\cap C_{2}|=3$. Moreover, by Claims 3 and 4, the
assumption $|(C\setminus A)\cap C_{2}|=2$ would mean that for the unique
colour $\delta\in(C\setminus A)\cap C_{3+}$ there is $i\in[5,6]$ such that
$(M)_{i,1}=\delta=(M)_{11-i,3}$; however, according to (9), $\delta$ has an
exemplar in $[5,6]\times[4,7]$, and so the colouring $f_{M}$ is not proper, a
contradiction.

Thus

$|(C\setminus A)\cap C_{3+}|=2.$ (10)

Because of a reasoning analogous to that above we see that each colour of
$(C\setminus A)\cap C_{3+}$ occupies exactly one position in
$[5,6]\times\\{1,3\\}$,

$(C\setminus A)\cap C_{3+}=C_{3+}^{1},$ (11)

and then, using (9),

$C_{3+}\subseteq\mathbb{R}(5)\cap\mathbb{R}(6).$ (12)

Now if $c_{4+}\geq 1$ (and, consequently, $c_{3+}=3$, which we have seen
already), then, by (24), (10) and (11), $c_{3+}^{1}=2$ and $c_{3+}^{2}=1$;
since $c_{2}^{1}\leq 3$, in such a case $c_{2}^{1}+c_{3+}^{1}+2c_{3+}^{2}\leq
7$ in contradiction with (6).

Therefore, in the rest of the proof of Claim 7 we work with $c_{4+}=0$,
$c_{3+}=4$, $c_{3+}^{1}=2$, $c_{3}^{2}=c_{3+}^{2}=2$ and $c_{2}^{1}=2$, see
(6), (24), (10), (11). Moreover, all positions in $S$ are occupied by colours
of $C_{2}^{1}\cup C_{3}^{2}$. If $\delta=(M)_{i,j}\in C_{2}^{1}$ with
$(i,j)\in\\{(1,3),(2,1)\\}$, then, because of (10), (11) and (12),
$\mathrm{exc}(\delta)\geq 1+|(C\setminus A)\cap C_{3+}|=1+c_{3+}^{1}=3$, a
contradiction.

Thus $\\{(M)_{1,3},(M)_{2,1}\\}\subseteq C_{3+}^{2}$, and for a 2-colour
$\varepsilon$ occupying a position in $[5,6]\times\\{1,3\\}$ (there are two
such colours), by (12) we have $\mathrm{exc}(\varepsilon)\geq c_{3+}-1=3$, a
contradiction again. $\blacksquare$

######  Claim 8.

If $i,k\in[1,6]$, $i\neq k$, then $r(i,k)\leq 2$.

Proof. The assumption $r(i,k)\geq 3$ would be in contradiction with Claim 6 or
Claim 7. $\blacksquare$

######  Claim 9.

No set $\\{\alpha,\beta,\gamma\\}\subseteq C_{2}$ is of the type
$(3^{1}2^{1}1^{1},3^{1}2^{1}1^{1})$.

Proof. Having in mind Claim 4 (or else Claim 7), assume (w)
$(M)_{1,1}=\alpha=(M)_{2,2}$, $(M)_{1,2}=\beta=(M)_{2,1}$ and
$(M)_{1,3}=\gamma=(M)_{3,1}$. Let $A^{1}$ be the set of colours occupying a
position in
$(\\{1\\}\times[4,7])\cup([4,6]\times\\{1\\})\cup\\{(2,3),(3,2)\\}$, $A^{n}$
the set of colours in $(\\{n\\}\times[4,7])\cup([4,6]\times\\{n\\})$ for
$n=2,3$, $A_{m}^{n}=C_{m}\cap A^{n}$ and $a_{m}^{n}=|A_{m}^{n}|$ for
$m\in\\{2,3+\\}$, $n\in[1,3]$. Then

$\displaystyle|A^{1}|=a_{2}^{1}+a_{3+}^{1}=9,$ (13)
$\displaystyle|A^{2}|=a_{2}^{2}+a_{3+}^{2}=7,$ (14) $\displaystyle A_{1}\cap
A_{2}=\emptyset,$ (15)

since otherwise $\mathrm{exc}(\alpha)\geq 3$. Moreover, $|A^{3}|\leq 7$ and
$A^{2}\subseteq A^{3}$ (each pair $\\{\gamma,\eta\\}$ with $\eta\in A_{2}$ is
good), hence, by (14),

$A_{2}=A_{3}.$ (16)

Let us show that distinct colours $\delta=(M)_{2,3}$, $\varepsilon=(M)_{3,2}$
(a consequence of (13)) satisfy

$\\{\delta,\varepsilon\\}\subseteq C_{3+}.$ (17)

Indeed, if $\eta=(M)_{i,5-i}\in\\{\delta,\varepsilon\\}\cap C_{2}$ for some
$i\in[2,3]$ and (w) $\eta=(M)_{4,4}$, then all colours appearing in
$(\\{i\\}\times[4,7])\cup([4,6]\times\\{5-i\\})\cup\\{(5-i,4),(4,i)\\}$ belong
to $A^{2}\setminus\\{\eta\\}$, hence, by (14) and (16),
$\mathrm{exc}(\eta)\geq 9-(7-1)=3$, a contradiction.

Further, with $\zeta=(M)_{3,3}$ we have

$\zeta\in C_{3+}\cap A^{1}.$ (18)

To see it realise first that, since the pair $\\{\zeta,\alpha\\}$ is good and
$f_{M}$ is proper, we get $\zeta\notin A^{2}\cup\\{\delta,\varepsilon\\}$ and
$\zeta\in A^{1}$. Moreover, $\zeta\in C_{3+}$, because the assumption
$\zeta\in\mathbb{R}_{2}(1)$ ($\zeta\in\mathbb{C}_{2}(1)$) contradicts Claim 7
(Claim 4, respectively).

By (13), (14) and Claim 2.4, we have

$a_{2}^{1}+a_{2}^{2}\geq(9+7)-c_{3+}\geq 12.$ (19)

Further, by (13), (14) and (17)–(19),

$\displaystyle 5\leq a_{2}^{1}\leq 6,$ (20) $\displaystyle 6\leq a_{2}^{2}\leq
7.$ (21)

Consider a colour $\eta\in A_{2}^{1}\cap\mathbb{R}(1)$ (from(20) we see that
there are at least two such colours), (w) $\eta=(M)_{1,j}=(M)_{4,l}$. Then
from $g(1,j,A_{2}^{2})\leq g(1,j,A^{2})=2$ and $g(4,l,A_{2}^{2})\leq
g(4,l,A^{2})\leq 4$ it follows that $a_{2}^{2}\leq 2+4=6$, hence, by (14),
(20), (21), $a_{2}^{1}=a_{2}^{2}=6$ and $a_{3+}^{2}=1$.

Suppose first $\zeta\in\mathbb{C}(1)$ so that all positions in
$\\{1\\}\times[4,7]$ are occupied by colours of $A_{2}^{1}$. If
$\eta=(M)_{1,j}$, $j\in[4,7]$, then proceeding similarly as above it is easy
to see that both positions in $[2,3]\times\\{j\\}$ are occupied by colours of
$A_{2}^{2}$. Thus $\mathbb{R}_{2}(2,3)$ consists of at least two colours of
$A_{2}^{2}$. By Claim 8 we obtain $r_{2}(2,3)=2$, (w)
$(M)_{2,4}=\vartheta=(M)_{3,5}$ and $(M)_{2,5}=\iota=(M)_{3,4}$. Now
$\kappa=(M)_{1,6}$ satisfies $\kappa\in\mathbb{C}(4)\cup\mathbb{C}(5)$ (the
pair $\\{\kappa,\vartheta\\}$ is good) and, analogously,
$\lambda=(M)_{1,7}\in\mathbb{C}(4)\cup\mathbb{C}(5)$. By Claim 6, the copies
of $\kappa,\lambda$ that are in $[4,6]\times[4,5]$ do not share a row, (w) one
of them is in $\mathbb{R}(4)$ and the other in $\mathbb{R}(5)$. Then, however,
reasoning similarly as above again, all positions in $[4,5]\times[2,3]$ are
occupied by colours of $A_{2}^{2}$. Consequently, the unique colour of
$A_{3+}^{2}$ is $(M)_{6,2}=(M)_{6,3}$, and $f_{M}$ is not proper.

If $\zeta\in\mathbb{R}(1)$, (w) $\zeta=(M)_{1,7}$, then all positions in
$(\\{1\\}\times[4,6])\cup([4,6]\times\\{1\\})$ are occupied by colours of
$A_{2}^{1}$, which implies that all positions in
$([2,3]\times[4,6])\cup([4,6]\times[2,3])$ are occupied by colours of
$A_{2}^{2}$. So, the unique colour of $A_{3+}^{2}$ is $(M)_{2,7}=(M)_{3,7}$, a
contradiction. $\blacksquare$

##  3 Final analysis

We are now ready to do the final analysis. Suppose (w) that $r_{2}(1)\geq
r_{2}(i)$ for $i\in[2,6]$, which, by Claim 2.3, implies

$7\geq
r_{2}(1)\geq\left\lceil\frac{2c_{2}}{6}\right\rceil\geq\left\lceil\frac{30}{6}\right\rceil=5.$
(22)

Given $r_{2}(1)$ we assume (w) that the sequence $S=(r_{2}(1,i))_{i=2}^{6}$ is
nonincreasing. Since $r_{2}(1)\in[5,7]$, we have
$r_{2}(1,2)\geq\lceil\frac{r_{2}(1)}{5}\rceil\geq 1$,
$r_{2}(1,6)\leq\lfloor\frac{r_{2}(1)}{5}\rfloor=1$, and Corollary 8 yields
$r_{2}(1,2)\leq 2$. We suppose (w) that

$j\in[1,r_{2}(1)]\Rightarrow(M)_{1,j}\in C_{2},$

and, more precisely,

$\displaystyle(M)_{1,1}=\alpha,\ (M)_{1,2}=\beta,\ (M)_{1,3}=\gamma,\
(M)_{1,4}=\delta,\ (M)_{1,5}=\varepsilon,$ $\displaystyle r_{2}(1)\geq
6\Rightarrow(M)_{1,6}=\zeta,\qquad r_{2}(1)=7\Rightarrow(M)_{1,7}=\eta.$

Let $p$ be the smallest integer in $[2,6]$ such that $r_{2}(1,i)\leq 1$ for
every $i\in[p,6]$; $p$ is correctly defined since $r_{2}(1,6)\leq 1$. Then

$r_{2}(1,i)=1\Leftrightarrow i\in[p,r_{2}(1)+3-p],$

and, counting the number of positions in $[2,6]\times[1,7]$ occupied by
colours of $\mathbb{R}_{2}(1)$, we obtain $2(p-2)\leq r_{2}(1)\leq
2(p-2)+(7-p)$, which yields

$r_{2}(1)-3\leq p\leq\left\lfloor\frac{r_{2}(1)+4}{2}\right\rfloor\leq 5.$
(23)

Moreover, because of Claims 6 and 7 we have

$\displaystyle p\geq 3$
$\displaystyle\Rightarrow((M)_{2,1}=\beta\land(M)_{2,2}=\alpha),$
$\displaystyle p\geq 4$
$\displaystyle\Rightarrow((M)_{3,3}=\delta\land(M)_{3,4}=\gamma),$
$\displaystyle p=5$
$\displaystyle\Rightarrow((M)_{4,5}=\zeta\land(M)_{4,6}=\varepsilon).$

Let $q_{j}=|\mathbb{R}_{2}(1)\cap\mathbb{C}(j)|$ for $j\in[1,7]$. By Claim 9
we know that a 2-colour $\mu$, which occupies a position in
$\\{1\\}\times[2p-3,r_{2}(1)]$, satisfies $\mu\notin\mathbb{C}(j)$ for every
$j\in[1,2p-4]$, hence $q_{j}=2$ for any $j\in[1,2p-4]$, and

$\sum_{j=2p-3}^{7}q_{j}=2[r_{2}(1)-(2p-4)]=2r_{2}(1)+8-4p;$ (24)

clearly,

$j\in[2p-3,7]\Rightarrow q_{j}\leq 3,$ (25)

since with $q_{j}\geq 4$ and $\mu\in\mathbb{R}_{2}(1)\cap\mathbb{C}(j)$ for
some $j\in[2p-3,7]$ we have $\mathrm{exc}(\mu)\geq q_{j}-1\geq 3$. Notice also
that

$j\in[2p-3,r_{2}(1)]\Rightarrow 1\leq q_{j}\leq\min(3,r_{2}(1)+4-2p),$ (26)

because 2-colours occupying a position in $[1,6]\times\\{j\\}$ are distinct
from $2p-4$ (2-)colours appearing in $\\{1\\}\times[1,2p-4]$. Moreover, we
assume (w) that the sequence $(q_{j})_{j=2p-3}^{r_{2}(1)}$ is nonincreasing,
and that, if $(r_{2}(1),p)=(5,2)$, the sequence
$(q_{1},q_{2},q_{3},q_{4},q_{5})$ is nonincreasing.

For every pair $(r_{2}(1),p)$ obeying (22) and (23), we analyse the set
$\mathcal{Q}(r_{2}(1),p)$ of sequences $(q_{j})_{j=2p-3}^{7}$ satisfying all
restrictions (24)–(26). More precisely, we show that the assumption that $M$
is characterised by an arbitrary sequence $Q\in\mathcal{Q}(r_{2}(1),p)$ leads
to a contradiction, mostly because of $\Sigma\geq 13$ (a contradiction to
Claim 2.10) or the existence of a line of $M$ containing at least five
3+colours (by Claim 2.4 then the colouring $f_{M}$ is not proper).

The structure of the sets $\mathcal{Q}(r_{2}(1),p)$ with
$(r_{2}(1),p)\neq(5,2)$ follows:

$\displaystyle\mathcal{Q}(7,5)=$ $\displaystyle\emptyset,$
$\displaystyle\mathcal{Q}(7,4)=$ $\displaystyle\\{(3,2,1),(2,2,2)\\},$
$\displaystyle\mathcal{Q}(6,5)=$ $\displaystyle\\{(0)\\},$
$\displaystyle\mathcal{Q}(6,4)=$ $\displaystyle\\{(2,2,0),(2,1,1),(1,1,2)\\},$
$\displaystyle\mathcal{Q}(6,3)=$
$\displaystyle\\{(3,3,1,1,0),(3,2,2,1,0),(3,2,1,1,1),(3,1,1,1,2),(2,2,2,2,0),$
$\displaystyle(2,2,2,1,1),(2,2,1,1,2),(2,1,1,1,3)\\},$
$\displaystyle\mathcal{Q}(5,4)=$ $\displaystyle\\{(1,1,0)\\},$
$\displaystyle\mathcal{Q}(5,3)=$
$\displaystyle\\{(3,2,1,0,0),(3,1,1,1,0),(2,2,2,0,0),(2,2,1,1,0),(2,1,1,2,0),$
$\displaystyle(2,1,1,1,1),(1,1,1,3,0),(1,1,1,2,1)\\}.$

As we shall see later, it is not necessary to know the structure of
$\mathcal{Q}(5,2)$ explicitly.

Our analysis is organised according to the following rules: All visible
colours in $M$ (those represented by Greek alphabet letters) are 2-colours,
and both copies of a visible colour are present in $M$. Asterisk entries in
$M$ represent $3+$colours. Some asterisk entries appear in $M$ by definition,
e.g., each asterisk entry in the first row of $M$ occupies a position in
$\\{1\\}\times[r_{2}(1)+1,7]$. Another reason why an asterisk entry appears in
$M$ is that, if the corresponding position is occupied by a 2-colour
$\lambda$, then putting another copy of $\lambda$ to a free position (i.e.,
one that is not occupied by a visible colour) in any proper way (so that the
resulting partial vertex colouring $f^{\prime}$ of $K_{6}\square K_{7}$ is
proper) leads to a situation, in which no continuation of $f^{\prime}$ to a
proper complete vertex colouring of $K_{6}\square K_{7}$ is possible, because
at least one pair $\\{\lambda,\mu\\}$, where $\mu$ is a visible colour, is not
good.

If $Q=(3,2,1)$, then (w) $(M)_{4,5}=\zeta$, $(M)_{5,5}=\eta$ and
$(M)_{6,6}=\varepsilon$, hence the set $\\{\varepsilon,\zeta\\}$ is of the
type $(2^{1}1^{2},2^{2})$, which contradicts Claim 4.

In the case $Q=(2,2,2)$ we are (w) in the situation of Fig. 4. If a 2-colour
$\mu$ occupies a position in $\\{k\\}\times[2l-1,2l]$ for some $k\in[4,6]$ and
$l\in[1,2]$, then $\mu=(M)_{4-l,h(k)}$, where
$h(k)=\frac{1}{2}(3k^{2}-31k+90)$, and $\nu\in C_{3+}$ for each colour $\nu$
occupying a position in $([4,6]\setminus\\{k\\})\times[5-2l,6-2l]$ (with
$\nu\in C_{2}$ the pair $\\{\mu,\nu\\}$ is not good). As a consequence, it is
easy to see that at least nine positions in $[4,6]\times[1,4]$ are occupied by
3+colours. Besides that, if $\mu=(M)_{i,j}\in C_{2}$ with
$(i,j)\in\\{(2,3),(2,4),(3,1),(3,2)\\}$, the second copy of $\mu$ must occupy
one of the positions $(4,7),(5,5),(6,6)$. Altogether we have $\Sigma\geq
3+9+1=13$.

$\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&\eta\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&\gamma&.&.&.\\\ .&.&.&.&\zeta&*&.\\\
.&.&.&.&.&\eta&*\\\
.&.&.&.&*&.&\varepsilon\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&\gamma&.&.&.\\\
.&.&.&.&\zeta&\varepsilon&.\\\ .&.&.&.&.&.&*\\\
.&.&.&.&.&.&*\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&\gamma&.&.&.\\\ .&.&.&.&\zeta&*&.\\\
.&.&.&.&.&.&\varepsilon\\\ .&.&.&.&.&*&*\end{pmatrix}$ $\hskip
2.84526pt\mathrm{Fig.\ 4}\hskip 93.89409pt\mathrm{Fig.\ 5}\hskip
93.89409pt\mathrm{Fig.\ 6}$

$Q=(0)$, Fig. 5: Because of $c_{2}(7)\geq 6-c_{3+}\geq 2$ we suppose (w)
$\eta=(M)_{2,7}\in C_{2}$ so that $\eta$ is in
$\\{(3,5),(3,6),(4,3),(4,4)\\}$.

Under the assumption $\eta\in\mathbb{R}(3)$ we have (w) $\eta=(3,5)$. Let
$C_{2}^{\prime}$ be the set of 2-colours occupying a position in
$[5,6]\times[1,6]$; clearly, $c_{3+}\leq 4$ implies $|C_{2}^{1}|\geq 6$. If
$\mu\in C_{2}^{\prime}$, then from the fact that each pair $\\{\mu,\nu\\}$
with $\nu\in C_{2}^{\prime\prime}=\\{\alpha,\beta,\gamma,\delta,\eta\\}$ is
good one easily gets that the second copy of $\mu$ occupies a position in
$[2,3]\times[1,6]$. As $g(4,7,C_{2}^{\prime\prime})=0$ and
$g(i,j,C_{2}^{\prime\prime})\leq 5$ provided that $(i,j)\in[2,3]\times[1,6]$
is a dot position, we obtain $\omega=(M)_{4,7}\in C_{3+}$ (notice that
$\omega\notin C_{2}^{\prime}$), hence $(M)_{3,7}\in C_{2}$. Then
$\mathrm{exc}(\eta)\geq 4$, since we can uncolour vertices $(i,j)$ with
$i\in[2,3]$ and $(M)_{i,j}\in C_{3+}$ (here we use $r_{3+}(i)\geq 1$ and
$C_{3+}\subseteq\mathbb{C}(7)$), as well as the vertices $(5,5),(6,5)$
(independently from the frequencies of $(M)_{5,5}$ and $(M)_{6,5}$) without
affecting the completeness of the colour class $\eta$ in the resulting partial
colouring.

In the case $\eta\in\mathbb{R}(4)$ we obtain a contradiction similarly as
above.

The assumption $Q=(2,2,0)$ means that (w) $(M)_{4,5}=\zeta$ and
$(M)_{5,6}=\varepsilon$, hence the type of the set $\\{\varepsilon,\zeta\\}$
is $(2^{1}1^{2},2^{2})$ in contradiction to Claim 4.

For $Q=(2,1,1)$ the situation is (w) depicted on Fig. 6. If
$\lambda=(M)_{6,j}\in C_{2}$, where $j\in[2k-1,2k]$ with $k\in[1,2]$, then
$\lambda=(M)_{4-k,5}$. As a consequence, $r_{3+}(6)=4$, $\eta=(M)_{6,5}\in
C_{2}$, and with $\mu=(M)_{2,5}$, $\nu=(M)_{3,5}$ we have
$\\{\mu,\nu\\}\subseteq\mathbb{R}(6)$. Then, however, $\mathrm{exc}(\eta)\geq
3$ ($\mu,\nu$ and at least one 3+colour contribute to the excess of $\eta$).

$Q=(1,1,2)$, Fig. 7: Similarly as above we see that $r_{3+}(6)=4$,
$\eta=(M)_{6,7}\in C_{2}$,
$\\{(M)_{2,7},(M)_{3,7}\\}\subseteq\mathbb{R}_{2}(6)$, and so
$\mathrm{exc}(\eta)\geq 4$.

If $Q=(3,3,1,1,0)$, then (w) $(M)_{3,3}=\delta,(M)_{4,3}=\varepsilon$ and
$\gamma\in\\{(M)_{5,4},$ $(M)_{6,4}\\}$ so that the type of the set
$\\{\gamma,\delta\\}$ contradicts Claim 4.

$\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&\gamma&.&.&.\\\
.&.&.&.&*&.&\varepsilon\\\ .&.&.&.&.&*&\zeta\\\
.&.&.&.&*&*&.\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&.&.&.&*\\\ .&.&\zeta&.&.&.&*\\\
.&.&.&\varepsilon&.&.&.\\\
.&.&.&.&\gamma&.&*\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&\bullet&\bullet&\bullet\\\
\bullet&\bullet&\delta&.&*&\bullet&*\\\
\bullet&\bullet&\varepsilon&.&*&\bullet&\bullet\\\
\bullet&\bullet&.&\zeta&\bullet&\bullet&\bullet\\\
\bullet&\bullet&.&.&\bullet&\bullet&\gamma\end{pmatrix}$ $\hskip
2.84526pt\mathrm{Fig.\ 7}\hskip 93.89409pt\mathrm{Fig.\ 8}\hskip
93.89409pt\mathrm{Fig.\ 9}$

If $Q=(3,2,2,1,0)$, then, having in mind Claim 4, we are (w) in the situation
of Fig. 8. Further, $\eta=(M)_{2,7}\in C_{2}$ and $\vartheta=(M)_{5,7}\in
C_{2}$, which implies $\eta=(M)_{5,3}$ and $\vartheta=(M)_{2,3}$.
Consequently, it is easy to see that both positions in $\\{(3,4),(4,6)\\}$ are
occupied by 3+colours, and, provided that $\mu=(M)_{i,j}\in C_{2}$ for some
$(i,j)\in[3,6]\times[1,2]$, then $(i,j)\in\\{(5,1),(5,2)\\}$ and
$\mu=(M)_{6,3}$. Therefore, $\Sigma\geq 4+2+7+r_{3+}(2)\geq 14$.

$Q=(3,2,1,1,1)$, (w) Fig. 9 (using Claim 4 again): If a bullet position is
occupied by a 2-colour $\mu$, then the second copy of $\mu$ occupies a dot
position. Therefore, $\Sigma\geq 4+(19-6)=17$.

$Q=(3,1,1,1,2)$, (w) Fig. 10: Analogously as in the case of Fig. 9 we obtain
$\Sigma\geq 5+(19-6)=18$.

Under the assumption $Q=(2,2,2,2,0)$ we have
$g(i,7,\\{\alpha,\beta,\gamma,\delta,\varepsilon,\zeta\\})=1$ for any
$i\in[3,6]$ and $g(k,l,\\{\alpha,\beta,\gamma,\delta,\varepsilon,\zeta\\})\leq
4$ for any position $(k,l)\in[2,6]\times[1,6]$ occupied by a colour of
$C\setminus\\{\alpha,\beta,\gamma,\delta,\varepsilon,\zeta\\}$, hence
$c_{3+}(7)\geq 5$, a contradiction.

$\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&\bullet&\bullet&\bullet&.\\\
\bullet&\bullet&\delta&*&\bullet&\bullet&.\\\
\bullet&\bullet&\varepsilon&\bullet&*&\bullet&.\\\
\bullet&\bullet&.&*&*&\bullet&\gamma\\\
\bullet&\bullet&.&\bullet&\bullet&\bullet&\zeta\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&\bullet&.&\bullet&\bullet\\\
.&.&.&\varepsilon&\bullet&\bullet&\bullet\\\
.&.&\bullet&.&\gamma&\bullet&\bullet\\\
.&.&.&.&.&*&\zeta\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&*&.&*&.\\\ .&.&.&\varepsilon&.&.&*\\\
.&.&.&.&\zeta&*&.\\\ .&.&.&.&.&.&\gamma\end{pmatrix}$ $\hskip
2.84526pt\mathrm{Fig.\ 10}\hskip 93.89409pt\mathrm{Fig.\ 11}\hskip
93.89409pt\mathrm{Fig.\ 12}$

If $Q=(2,2,2,1,1)$, because of Claim 4 (w) there are two possibilities for the
structure of $M$, see Figs. 11 and 12.

In the case of Fig. 11 a bullet position can be occupied by a 2-colour only if
the second copy of that colour appears in $\\{2\\}\times[3,5]$. A position in
$\\{(2,6),(2,7),(6,1),(6,2)\\}$ is occupied by a 2-colour only if the second
copy of that colour is in $\\{(3,5),(4,3),(5,4)\\}$. Further, it is easy to
see that at most one of two colours in $\\{i\\}\times[1,2]$ with $i\in[3,5]$
is a 2-colour (which is in $\\{6\\}\times[3,5]$). Therefore $\Sigma\geq
2+(9-3)+(4-3)+3\cdot 1+r_{3+}(2)\geq 13$.

In the situation of Fig. 12 let $k=\max(i\in\\{2,3,5\\}:(M)_{i,7}\in C_{2})$
and $\eta=(M)_{k,7}$. The assumption $k=2$ implies
$\eta\in\\{(M)_{3,5},(M)_{5,4}\\}$.

$\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&.&.&\eta\\\ .&.&\delta&*&\eta&*&*\\\
*&*&.&\varepsilon&.&.&*\\\ *&*&.&.&\zeta&*&*\\\
*&*&.&.&.&.&\gamma\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&.&.&\eta\\\ *&*&\delta&*&.&*&*\\\ .&.&.&\varepsilon&.&.&*\\\
.&.&.&\eta&\zeta&*&*\\\
*&*&.&.&.&.&\gamma\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&\eta&.&.\\\ .&.&\delta&*&.&*&\eta\\\
*&*&.&\varepsilon&.&.&*\\\ *&*&.&.&\zeta&*&*\\\
.&.&*&.&.&.&\gamma\end{pmatrix}$ $\hskip 2.84526pt\mathrm{Fig.\ 13}\hskip
93.89409pt\mathrm{Fig.\ 14}\hskip 93.89409pt\mathrm{Fig.\ 15}$

If $\eta=(M)_{3,5}$, see Fig. 13, then $\Sigma\geq 13+r_{3+}(2)\geq 14$.

In the case $\eta=(M)_{5,4}$ depicted in Fig. 14 we have $r_{3+}(3)\geq 5$.

If $k=3$ (Fig. 15), then $\eta=(M)_{2,5}$, and from $r_{3+}(2)\geq 1$ it
follows that $\mathrm{exc}(\alpha)\geq 3$, a contradiction.

Fig. 16 corresponds to $k=5$, requiring $\eta=(M)_{2,4}$. If $\vartheta\in
C_{2}$ is in $\\{4\\}\times[1,2]$, then $\vartheta=(M)_{5,3}$, and, if
$\iota\in C_{2}$ is in $\\{6\\}\times[1,2]$, then $\iota=(M)_{5,4}$. So,
$c_{3+}(1)+c_{3+}(2)\geq 4$, which implies $\mathrm{exc}(\alpha)\geq 3$.

$\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&\eta&.&.&.\\\ *&*&\delta&*&.&*&.\\\ .&.&.&\varepsilon&.&.&*\\\
.&.&.&.&\zeta&*&\eta\\\
.&.&.&.&.&*&\gamma\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&.&.&*&.\\\ .&.&.&\varepsilon&*&.&.\\\
.&.&*&.&*&.&\gamma\\\
.&.&.&.&.&*&\zeta\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&\zeta&*\\\
\beta&\alpha&.&\bullet&\bullet&\bullet&.\\\
\bullet&\bullet&\delta&\bullet&\bullet&\bullet&.\\\
\bullet&\bullet&.&\bullet&*&*&\gamma\\\
\bullet&\bullet&.&\bullet&*&\bullet&\varepsilon\\\
\bullet&\bullet&.&\bullet&\bullet&*&\zeta\end{pmatrix}$ $\hskip
2.84526pt\mathrm{Fig.\ 16}\hskip 93.89409pt\mathrm{Fig.\ 17}\hskip
93.89409pt\mathrm{Fig.\ 18}$

In the case $Q=(2,2,1,1,2)$, using Claim 4, (w) the description by Fig. 17
applies. Claim 9 implies that a 2-colour occupying a position in
$[3,6]\times[1,2]$ does not appear in $\\{2\\}\times[3,7]$. Therefore, it is
easy to see that for any $i\in[3,6]$ at most one of the positions in
$\\{i\\}\times[1,2]$ is occupied by a 2-colour; as a consequence of
$c_{3+}\leq 4$ and $r_{3+}(2)\geq 1$ then $\mathrm{exc}(\alpha)\geq 3$.

If $Q=(2,1,1,1,3)$, then (w) we have the situation of Fig. 18 with $\Sigma\geq
5+(19-6)=18$ (reasoning as in Fig. 9).

$\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&*&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&\gamma&.&.&.\\\
.&.&.&.&.&\varepsilon&.\\\ .&.&.&.&.&.&*\\\
.&.&.&.&.&.&*\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&*&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&\bullet&.&.&\bullet\\\
.&.&\varepsilon&.&\bullet&.&\bullet\\\ .&.&.&.&.&\gamma&\bullet\\\
.&.&.&\bullet&\bullet&\bullet&\bullet\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&*&*\\\
\beta&\alpha&.&.&.&\bullet&\bullet\\\ .&.&\delta&.&.&.&.\\\
.&.&.&\varepsilon&.&.&.\\\ .&.&.&.&\gamma&.&.\\\
\bullet&\bullet&.&.&.&*&*\end{pmatrix}$ $\hskip 2.84526pt\mathrm{Fig.\
19}\hskip 93.89409pt\mathrm{Fig.\ 20}\hskip 93.89409pt\mathrm{Fig.\ 21}$

Clearly, if $r_{2}(1)=5$, then $r_{2}(i)=5$ and $r_{3+}(i)=2$ for each
$i\in[1,6]$, hence $c_{2}=\frac{1}{2}\sum_{i=1}^{6}r_{2}(i)=15$, and, by
Claims 2.5, 2.6, $c_{3+}=c_{3}=4$.

If $Q=(1,1,0)$, we are (w) in the situation of Fig. 19. Each colour of
$\mathbb{C}_{2}(7)$ has its second copy in $[2,4]\times[1,6]$, hence at least
$5+2c_{2}(7)+\sum_{i=2}^{4}r_{3+}(i)=11+2c_{2}(7)\geq 15$ positions in
$[2,4]\times[1,7]$ are occupied by colours of
$\\{\alpha,\beta,\gamma,\delta,\varepsilon\\}\cup\mathbb{C}_{2}(7)\cup
C_{3+}$. Since a colour in $\mathbb{R}_{2}(5)\cup\mathbb{R}_{2}(6)$ has its
second copy in $[2,4]\times[1,6]$, we have $r_{2}(5)+r_{2}(6)\leq 18-(15-3)=6$
and $4=r_{3+}(5)+r_{3+}(6)=14-[r_{2}(5)+r_{2}(6)]\geq 8$, a contradiction.

If $Q=(3,2,1,0,0)$, then the set $\\{\gamma,\delta\\}\subseteq C_{2}$ is of
the type $(2^{1}1^{2},2^{2})$, which contradicts Claim 4.

$Q=(3,1,1,1,0)$, (w) Fig. 20: A bullet position can be occupied by a colour
$\mu\in C_{2}$ only if $\mu=(M)_{2,3}$. That is why $r_{3+}(6)\geq 3$, a
contradiction.

$Q=(2,2,2,0,0)$, (w) Fig. 21: If a bullet position is occupied by a colour
$\mu\in C_{2}$, then $\mu\in\\{(M)_{3,5},(M)_{4,3},(M)_{5,4}\\}$. One can
easily see that if $i\in[3,5]$, then at most one of colours in
$\\{i\\}\times[6,7]$ is a 2-colour. Therefore, if $(M)_{2,j}\in C_{3+}$ for
both $j=6,7$, then $c_{3+}(6)+c_{3+}(7)\geq 3\cdot 2+3\cdot 1=9$, and there is
$j\in[6,7]$ with $c_{3+}(j)\geq 5$, a contradiction. Thus, there is
$j\in[6,7]$ with $(M)_{2,j}\in C_{2}$. Then, however, since
$(M)_{6,1},(M)_{6,2}\in C_{2}$ (a consequence of $r_{3+}(6)=2$), the pair
$\\{(M)_{2,j},(M)_{6,l}\\}$ is not good for $l=1,2$.

If $Q=(2,2,1,1,0)$, then (w), by Claim 4, the situation is depicted in Fig.
22. If a 2-colour $\mu$ is in $\\{(2,7),(6,1),(6,2)\\}$, then
$\mu\in\\{(M)_{4,3},(M)_{5,4}\\}$, and if a 2-colour $\nu$ is in
$\\{(5,7),(6,6)\\}$, then $\nu=(M)_{2,4}$. From $r_{3+}(6)=2$ it follows that
there is a 2-colour $\zeta$ in $\\{6\\}\times[1,2]$; as a consequence then
$\omega=(M)_{2,7}\in C_{3+}$ (with $\omega\in C_{2}$ the pair
$\\{\omega,\zeta\\}$ is not good), $\eta=(M)_{5,7}=(M)_{2,4}\in C_{2}$,
$(M)_{6,6}\in C_{3+}$, and each colour, occupying a position in
$\\{6\\}\times[1,2]$, is a 2-colour. In such a case, however, with
$\vartheta=(M)_{4,3}\in\\{(M)_{6,1},(M)_{6,2}\\}$ the pair
$\\{\vartheta,\eta\\}$ is not good.

$Q=(2,1,1,2,0)$, (w) Fig. 23: If $\zeta\in\\{(M)_{3,7},(M)_{6,4}\\}\cap
C_{2}$, then $\zeta=(M)_{2,6}$, and if $\eta\in\\{(M)_{5,7},(M)_{6,5}\\}\cap
C_{2}$, then $\eta=(M)_{2,3}$. Therefore, at least two positions in
$\\{(3,7),(5,7),(6,4),(6,5)\\}$ are occupied by 3+colours. Since
$c_{3+}(7)\leq 4$, at most one position in $\\{(3,7),(5,7)\\}$ and at least
one position in $\\{(6,4),(6,5)\\}$ is occupied by a 3+colour. Further, from
$r_{3+}(6)=2$ it follows that exactly one position in $\\{(6,4),(6,5)\\}$ and
in $\\{(3,7),(5,7)\\}$ as well is occupied by a 3+colour. Consequently, by
Claim 6, $(M)_{2,7}$, $(M)_{6,1}$ and $(M)_{6,2}$ are three distinct
2-colours; this, however, leads to a contradiction, because if
$\vartheta\in\\{(M)_{2,7},(M)_{6,1},(M)_{6,2}\\}\cap C_{2}$, then necessarily
$\vartheta\in\\{(M)_{3,6},(M)_{5,3}\\}$.

If $Q=(1,1,1,3,0)$, we have (w)
$\\{\gamma,\delta,\varepsilon\\}\cap\mathbb{R}(6)=\emptyset$. If a position in
$\\{6\\}\times([1,5]\cup\\{7\\})$ is occupied by a 2-colour $\zeta$, then
$\zeta=(M)_{2,6}$, which yields $r_{3+}(6)\geq 5$, a contradiction.

$\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&*&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&.&.&.&*\\\ .&.&.&\varepsilon&.&.&.\\\
.&.&.&.&.&\gamma&.\\\
.&.&.&.&.&.&*\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&*&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&\delta&.&.&.&.\\\ .&.&.&.&.&\gamma&*\\\
.&.&.&.&.&\varepsilon&.\\\
.&.&.&.&.&.&*\end{pmatrix}\begin{pmatrix}\alpha&\beta&\gamma&\delta&\varepsilon&*&*\\\
\beta&\alpha&.&.&.&.&.\\\ .&.&*&.&.&\gamma&.\\\ .&.&.&*&.&\delta&.\\\
.&.&.&.&.&.&\varepsilon\\\ .&.&*&*&.&.&.\end{pmatrix}$ $\hskip
2.84526pt\mathrm{Fig.\ 22}\hskip 93.89409pt\mathrm{Fig.\ 23}\hskip
93.89409pt\mathrm{Fig.\ 24}$

If $Q=(1,1,1,2,1)$, the situation is (w) described by Fig. 24. If a 2-colour
$\zeta$ is in $\\{6\\}\times[1,2]$, then $\zeta=(M)_{5,6}$, hence
$r_{3+}(6)\geq 3$.

If $Q\in\mathcal{Q}(5,2)$, we have $\sum_{j=1}^{7}q_{j}=10$. Let
$J=\\{j\in[1,7]:q_{j}\geq 2\\}$. If $|J|\leq 3$, realise that any colour
$\zeta\in C_{2}\setminus\\{\alpha,\beta,\gamma,\delta,\varepsilon\\}$ requires
existence of a sufficient pair $(i,j)\in[2,6]\times[1,7]$, i.e., one
satisfying $g(i,j,\\{\alpha,\beta,\gamma,\delta,\varepsilon\\})\geq 3$. If
$(i,j)$ is a sufficient pair, then necessarily $j\in J$. Moreover, given $j\in
J$, the number of sufficient pairs $(i,j)$ is at most three. This is certainly
true if $q_{j}=3$. On the other hand, if $q_{j}=2$ and $(M)_{k,l}=(M)_{1,j}$
with $k\neq 1$, then, by Claim 7 and the fact that $p=2$,
$(M)_{k,j}\notin\\{\alpha,\beta,\gamma,\delta,\varepsilon\\}$, which means
that $g(k,j,\\{\alpha,\beta,\gamma,\delta,\varepsilon\\})=2$, and there are at
most three $i$’s such that the pair $(i,j)$ is sufficient. Therefore,
$c_{2}\leq 5+3\cdot 3=14$, which contradicts Claim 2.3.

So, we have $|J|\geq 4$. If $q_{1}=3$, then $10=\sum_{j=1}^{7}q_{j}\geq
3+3\cdot 2+1\cdot 1=10$, hence $q_{2}=q_{3}=q_{4}=2$, $q_{5}=1$ and
$q_{6}=q_{7}=0$. If $\zeta=(M)_{i,j}\in C_{2}$ with
$(i,j)\in[2,6]\times[6,7]$, then, since
$g(i,j,\\{\alpha,\beta,\gamma,\delta,\varepsilon\\})=1$, we have
$\zeta\in\mathbb{C}_{2}(1)\setminus\\{\alpha,\beta,\gamma,\delta,\varepsilon\\}$.
Thus $c_{3+}(6)+c_{3+}(7)\geq 2+(10-3)=9$, and there is $j\in[6,7]$ with
$c_{3+}(j)\geq 5$, a contradiction.

If $q_{1}\leq 2$, then
$g(i,j,\\{\alpha,\beta,\gamma,\delta,\varepsilon\\})\leq q_{j}+1\leq
q_{1}+1\leq 3$ for every $(i,j)\in[2,6]\times[1,5]$, hence
$g(k,l,\\{\alpha,\beta,\gamma,\delta,\varepsilon\\})\geq 2$ whenever
$(k,l)\in[2,6]\times[6,7]$ and $(M)_{k,l}\in C_{2}$, which implies $q_{l}\geq
1$, $l=6,7$. As a consequence then $10=\sum_{j=1}^{7}q_{j}\geq
2|J|+(7-|J|)=|J|+7\geq 11$, a final contradiction proving Theorem 3. ∎

Acknowledgements. This work was supported by the Slovak Research and
Development Agency under the contract APVV-19-0153.

## References

  * [1] A. Bouchet, Indice achromatique des graphes multiparti complets et réguliers, Cahiers du Centre d’Études de Recherche Opérationelle 20 (1978) 331–340.
  * [2] N.P. Chiang, H.L. Fu, On the achromatic number of the cartesian product $G_{1}\times G_{2}$, Australas. J. Combin. 6 (1992) 111–117.
  * [3] N.P. Chiang, H.L. Fu, The achromatic indices of the regular complete multipartite graphs, Discrete Math. 141 (1995) 61–66.
  * [4] F. Harary, S. Hedetniemi, G. Prins, An interpolation theorem for graphical homomorphisms, Portug. Math. 26 (1967) 454–462.
  * [5] M. Horňák, The achromatic number of $K_{6}\square K_{q}$ equals $2q+3$ if $q\geq 41$ is odd, arXiv:2009.06955v1 [math.CO].
  * [6] M. Horňák, The achromatic number of the Cartesian product of $K_{6}$ and $K_{q}$, arXiv:2009.07521v1 [math.CO].
  * [7] M. Horňák, Š. Pčola, Achromatic number of $K_{5}\times K_{n}$ for large $n$, Discrete Math. 234 (2001), 159–169.
  * [8] M. Horňák, Š. Pčola, Achromatic number of $K_{5}\times K_{n}$ for small $n$, Czechoslovak Math. J. 53 (128) (2003), 963–988.
  * [9] M. Horňák, J. Puntigán, On the achromatic number of $K_{m}\times K_{n}$, in: M. Fiedler (ed.), Graphs and Other Combinatorial Topics, Teubner, Leipzig, 1983, pp. 118–123.
  * [10] W. Imrich, S. Klavžar, Product Graphs, Wiley-Interscience, New York, 2000.


# Segmentation Consistency Training: Out-of-Distribution Generalization for
Medical Image Segmentation

Birk Torpmann-Hagen
University of Oslo
<EMAIL_ADDRESS>
&Vajira Thambawita
SimulaMet
<EMAIL_ADDRESS>
&Kyrre Glette
University of Oslo
<EMAIL_ADDRESS>
&Pål Halvorsen
SimulaMet
<EMAIL_ADDRESS>
&Michael A. Riegler
SimulaMet
<EMAIL_ADDRESS>

###### Abstract

Generalizability is seen as one of the major challenges in deep learning, in
particular in the domain of medical imaging, where a change of hospital or in
imaging routines can lead to a complete failure of a model. To tackle this, we
introduce Consistency Training, a training procedure and alternative to data
augmentation based on maximizing models’ prediction consistency across
augmented and unaugmented data in order to facilitate better out-of-
distribution generalization. To this end, we develop a novel region-based
segmentation loss function called Segmentation Inconsistency Loss (SIL), which
considers the differences between pairs of augmented and unaugmented
predictions and labels. We demonstrate that Consistency Training outperforms
conventional data augmentation on several out-of-distribution datasets on
polyp segmentation, a popular medical task.

##  1 Introduction

The last decade or so has seen a veritable revolution in artificial
intelligence. This has in large part been spearheaded by advancements in deep
learning, the remarkable performance of which it can be argued has rendered
more conventional approaches practically obsolete. Recent work has, however,
highlighted that Deep Neural Networks (DNNs) are highly prone to exhibiting
significant reductions in performance when deployed in practical settings or
otherwise Out of Distribution (OOD) data, in spite of the fact that they
readily exhibit high performance when evaluated on previously unseen subsets
of the training data [9, 11, 18, 15]. This is referred to as generalization
failure.

Recent analyses attribute generalization failure to a structural misalignment
between the features that a given model learns through Empirical Risk
Minimization (ERM) and the causal structure which it ideally should encode
[19, 11, 4, 26]. Generally, this misalignment occurs as a result of the
predictor - i.e., the trained model - learning spurious or otherwise causally
unrepresentative features that nonetheless perform well within the training
distribution. This is often referred to as shortcut learning [11] or the
Clever Hans effect [21]. This behaviour is of course made evident as soon as
the predictor is exposed to any form of distributional shift which breaks
these shortcuts, at which point it will fail to generalize. These
distributional shifts can range in magnitude, from common corruptions such as
noise or blurs [15] or spatial transforms [10], to practically imperceptible
perturbations, typically exemplified by adversarial attacks [6], or as will be
shown in this work; simply collecting data from different centers [29]. ERM
does not and cannot guarantee invariance to these sorts of distributional
shifts, as it assumes that the distribution of the training data is
Independent and Identically Distributed (IID) to the true distribution [13].

Closely related to shortcut learning is underspecification [9]. A machine
learning pipeline can be considered underspecified when it can return any
number of risk-equivalent predictors when evaluated on an IID holdout set,
dependent only on the random variables used within the training procedure -
i.e., dropout, weight initialization, and so on. Even with identical
hyperparameters, a given training procedure can return any number of
predictors, each having learned different patterns within the dataset. One
predictor may have learned one shortcut, another may have learned a different
shortcut, and the next may actually have learned features that correspond to
the causal structure it is intended to learn. With ERM, and in particular with
In-Distribution (InD)-oriented evaluation procedures, these are all
erroneously considered equivalent.

EndoCV2021 provided an opportunity to investigate generalization failure and
means by which to counteract them in the context of detection- and
segmentation of colorectal polyps via a competition [3]. Though several teams
made good progress towards increasing generalizability, the organizers’ review
of the submissions [1] highlighted that every submitted model nevertheless
exhibited significant performance reductions on the provided OOD datasets.
Moreover, though a multitude of methods and approaches were tested, many of
which did indeed benefit generalizability, few methods stood out as having the
potential for significant further development.

To address these shortcomings, we introduce Consistency Training. We re-frame
the problem of learning generalizable features into a matter of learning to
not learn spurious features. This framework requires a perturbation model,
which we in this work implement as simple data augmentation, and a
differentiable quantity that represents the consistency of the predictions
across perturbed and unperturbed inputs images, which we implement as
Segmentation Inconsistency Loss (SIL), a Jaccard-like loss function that
quantifies the degree to which the segmentation probability maps exhibit
unwarranted change after the input is perturbed. This loss function is then
used in conjunction with a task-specific loss, in this work Jaccard loss. To
increase the stability of the training routine, we also implement a dynamic
weighting procedure for the two constituent components of the overall loss
function. We show that Consistency Training increases generalization by a
significant margin on all tested datasets when compared to conventional data
augmentation. This framework is in other words a more performant alternative
to data augmentation. Consistency Training leads to increased generalization
with no additional overhead asides from the added computational cost involved
with computing the auxiliary loss term and the memory required to store
augmented and un-augmented versions of each batch. We summarize our
contributions as following:

  * •

We introduce SIL, a novel region-based segmentation loss function which
quantifies the inconsistency between two predicted segmentations when the
inputs are subjected to arbitrary augmentations.

  * •

We propose a robust method of incorporating this loss function without a loss
of segmentation performance through a dynamic weighting method.

  * •

We demonstrate quantitatively that Consistency Training increases
generalization when compared to data augmentation on three OOD datasets.

##  2 Related Work

Generalization Failure.  The development of consistency training was in large
part informed by recent advances in the understanding of generalization
failure. D’Amour et al. [9] perform a thorough analysis of generalization
failure through multiple case studies and highlight the role of
underspecification therein. Geirhos et al. [11] explore the idea of shortcut
learning in a similar manner, and highlight the importance of learning
causally related features. Schölkopf [26] discusses the importance of
causality in machine learning and how it relates to generalization failure.

Generalizable Training Methods.  Increasing generalizability is an open
problem, and there exists a large diversity of different approaches and
perspectives on the matter in the literature. Arjovsky et al. [4] develop a
novel training paradigm that makes use of multiple training environments in
order to increase generalization. Robey et al. [23] employ a similar method
and develop a model-based training paradigm which attempts to induce
invariance to learned mappings between training environments. Sandfort et al.
[25] also leverage generative networks, but instead simply use generated CT-
images as data augmentation, which they show improves OOD performance. Gokhale
et al. [12] compare the use of multiple data modification methods on
robustness and generalization and find that data augmentation improves
generalizability by a significant margin. Finally, Hendrycks et al. [16]
incorporate a consistency term into their loss function, in particular Jensen-
Shannon distance between output probabilities - in order to facilitate
robustness to distributional shifts for the image-classification task.

Generalizable Polyp Segmentation.  In the context of polyp-segmentation, this
work was motivated in large part by the findings in the proceedings of
EndoCV2021 [3], which through the evaluation of submissions on multiple OOD
datasets highlighted the significance of generalization failure. The winning
submission to EndoCV2021, submitted by Thambawita et al. [30], leverages an
ensemble-network in order to increase generalizability. Honga et al. [17] also
implement an ensemble-based model, which they show improves generalization. Gu
et al. [14] make use of domain composition and attention in an attempt to
generalize to unseen domains.

In this regard, the existing works do not work well in the context of
generalizability. Therefore, we introduced a novel training method with a new
loss function to improve the generalizability of segmentation models on out-
of-distribution datasets.

##  3 Approach

###  3.1 Consistency Training Method

This section will introduce Consistency Training, a training procedure wherein
the objective is to optimize for invariance to a set of various image
transformations by quantifying the degree to which the model outputs
inconsistent predictions when its input is subjected to some transformations.
This is achieved by giving the model two images: one which is augmented, and
one which is not. These inputs are then passed through the model, resulting in
two segmentation masks. The difference between these two predictions is then
computed, and compared to the difference (if any) between the augmented and
unaugmented segmentation labels. This is then incorporated into the loss-
function such that the discrepancy between the expected prediction change and
actual prediction change is minimized. This is illustrated in Figure 1. The
next sections will cover the theoretical basis of this training procedure as
well as the implementation of its constituent components.

Figure 1: Diagram showing Consistency Training. The CNN is given two images,
where one is simply an augmented version of the other. It then outputs two
segmentations, which in conjunction with the labels for both images is used to
compute SIL. The InD mIoU is then calculated, and used as weights for this
term and a segmentation loss, in our case Jaccard loss.

###  3.2 Quantifying Segmentation Consistency

Let $Y:=\\{y,\hat{y}:=f(x)\\}$ be the set consisting of the segmentation
labels (masks) and predictions for the unperturbed samples, where $f(\cdot)$
as before denotes the segmentation model. Let $\epsilon(\cdot)$ be some
perturbation function. Then, let
$A:=\\{a:=\epsilon(y),\hat{a}:=f(\epsilon(x))\\}$ be the set consisting of
masks and segmentation predictions when the input is subjected to a
perturbation. Segmentation Inconsistency can then be quantified as:

$\overline{\mathcal{C}}(y,a,\hat{y},\hat{a})=\frac{\sum\\{y\ominus\hat{y}\ominus
a\ominus\hat{a}\\}}{\sum\\{y\cup a\cup\hat{y}\cup\hat{a}\\}}$ (1)

$\ominus$ here denotes the symmetric difference/disjunctive union.
Equivalently, Segmentation Consistency can be expressed by:

$\mathcal{C}(y,a,\hat{y},\hat{a})=\frac{\sum\\{y\cup\hat{y}\cup
a\cup\hat{a}\\}\ominus\\{y\ominus\hat{y}\ominus
a\ominus\hat{a}\\}}{\sum\\{y\cup a\cup\hat{y}\cup\hat{a}\\}}$ (2)

These formulations are related by:

$\mathcal{C}(y,a,\hat{y},\hat{a})=1-\overline{\mathcal{C}}(y,a,\hat{y},\hat{a})$

In simple terms, this quantity corresponds to counting the number of pixels
that change after the input is subjected to a
perturbation,$\hat{a}\ominus\hat{y}$, but discounting those we expect to
change, $a\ominus y$. This is shown in Figure 2.

Figure 2: Visualisation of the operations used when computing segmentation-
consistency and -inconsistency. Segmentation Inconsistency
$(\overline{\mathcal{C}}$ considers the ratio of pixel-predictions that
underwent change as a result of a perturbation (here: augmentation), but
should not have. Conversely, Segmentation Consistency $\mathcal{C}$ considers
the ratio of predictions that changed accordingly with respect to the
perturbation.

Inconsistency as expressed in Equation 1 is not differentiable, and thus it
cannot in its current state be used as a part of a loss function. Thus, a
smooth extension of this metric is needed which can be achieved in much the
same way as how the Jaccard loss can be derived from the Jaccard index - i.e.,
by using differentiable versions of the set functions.

We can extend the definition of the symmetric difference to
$\Theta(A,B)=A(1-B)+B(1-A)$. This, naturally, is equivalent to the standard
symmetric difference if the values of A and B are binary. Similarly, the union
operator can be extended as $\bigcup(A,B)=A+B-AB$, and the intersection
operator as $\bigcap(A,B)=AB$. Like its binary equivalents, these operators
maintain their associative and commutative properties. One can optimize for
consistency by replacing the operators in Equation 1 with these functions,
which in turn can be used as a loss function:

$L_{sil}(y,\hat{y},a,\hat{a})=\sum\frac{\Theta(y,\hat{y},a,\hat{a})}{\bigcup(y,\hat{y},a,\hat{a})}$
(3)

This loss function will from this point be referred to as SIL. Note that
though this loss is implemented for binary segmentation in this task, it can
be extended to multi-class segmentation by computing it for each channel and
then reducing over channels.

###  3.3 Incorporating Consistency into Training

Using SIL as a loss function on its own is not really useful since it only
expresses inconsistency, and is to a large extent agnostic to whatever object
it is trying to segment. To illustrate, consider a model that predicts that
every pixel is positive regardless of the content of the image, and that the
augmentation strategy does not make use of augmentations that affect the
labels. In this case, the consistency term will always be zero. For example,
if the augmentation being performed is simply additive noise, the
inconsistency term is equally well minimized if the model learns to predict
that every pixel is positive as it would be if the model learned to be robust
to additive noise. Consequently, it has to be combined with a segmentation
loss, for instance Jaccard loss. A simple way to do this would be to simply
add them together and normalize, i.e.:

$L(Y,A)=\frac{1}{2}\big{[}L_{seg}(Y)+L_{sil}(Y,A)\big{]}$

Preliminary experiments showed that this, however, exhibited some degree of
instability during training. The model would readily get stuck in local minima
where its predictions were indeed consistent, but also consistently predicting
artifacts. Examples of this can be found in the Appendix.

To mitigate this, it is possible to employ a weighting strategy. Instead of
simply adding the respective losses together, one may weight the individual
components adaptively according to the InD segmentation performance, for
instance mIoU. This way, the model will learn to predict generally correct
segmentations early in the training, then start weighting consistency and as a
result generalization more and more as the model sees improvements to its
segmentation performance:

$L=(1-IoU)\times L_{seg}+IoU\times L_{c}$ (4)

Using this formulation, the model will start off trying to learn features that
contribute to generally improved segmentation performance, then as
segmentation performance improves start principally focusing on learning to be
consistent. If the model starts veering into areas in the loss-landscape that
constitute poor segmentation performance, it will self-correct by weighing the
segmentation loss more. In the implementation used in this study, the mIoU
weights were calculated on a per-batch basis such that the model can quickly
adapt if either of the respective objectives exhibit a degradation in
performance during training.

##  4 Experiments and Results

To determine the generalizability of our methods, we trained ten instances
each of four separate models using Consistency Training, as as well as with
conventional data augmentation and no augmentation, which served as baselines.
The generalizability of these models was then determined through computing
mIoU on three OOD datasets. The mIoUs for models trained with Consistency
training was then compared to the mIoUs of the two baselines across the three
OOD datasets to ascertain the extent to which it impacts generalization.

###  4.1 Experimental Setup

Models.  To evaluate the impact of Consistency Training sufficiently, it was
tested across a range of different models. These models include DeepLabV3+
[8], Feature Pyramid Network (FPN) [22], UNet [24], and Tri-Unet [30].

The models were implemented in pytorch using the segmentation-models-pytorch
library [31], using the library’s default values. This includes initialization
with Imagenet-pretrained weights. Ten instances of each model were trained
across each configuration in order to perform statistical analysis.

Datasets.  Evaluating the the generalizability of a given predictor requires
testing it on OOD data. Though this can to some extent be achieved by
carefully designing stress-tests [9], a more straight-forward approach is to
simply leverage existing OOD datasets. To this end, a number of polyp-
segmentation datasets were selected. The names, sizes, resolutions and
availabilities of these datasets is shown in Table 1. Sample images and masks
from the datasets can be seen in Figure 3. Kvasir-SEG was selected as the
training dataset, and partitioned into a 80/10/10 split as
training/validation/test data.

Table 1: Dataset Overview. The training dataset is marked using "*". Dataset |  Resolution |  Size |  Availability
---|---|---|---
Kvasir-SEG* [20] |  Variable |  1000 |  Public
Etis-LaribDB [28] |  1255x966 |  196 |  Public
CVC-ClinicDB [5] |  388x288 |  612 |  Public
EndoCV2020 [2] |  Variable |  127 |  On Request
Kvasir-SEG | Etis-LaribDB | CVC-ClinicDB | EndoCV2020
---|---|---|---
|  |  |
|  |  |
|  |  |
|  |  |
Figure 3: Sample images from the datasets. Kvasir-SEG (left column) was used
as the training data, the remaining datasets are test-sets.

Metrics We used two metrics to evaluate generalizability. To evaluate raw
performance, we used mIoU, which is defined as follows:

$IoU(y,\hat{y})=\frac{\sum\\{y=\hat{y}\\}}{\sum\\{y=1\\}\cup\\{\hat{y}=1\\}\\}}$

Measuring the mIoU scores across all the aforementioned datasets, naturally,
provides an indication of the generalizability of the given predictor. Though
it is of course impossible to account for all distributional shifts that may
occur in deployment, high degrees of generalization across multiple datasets
should nevertheless indicate a sufficient level of generalization.

Statistical tests Two different tests were used to ascertain statistical
significance. In cases where the mIoUs distribution was approximately normally
distributed, for instance when comparing mIoU samples for a given pair of
models on one dataset, an independent-sample t-test was used. When comparing
across models, the Mann-Whitney U-test was chosen due to the multi-modality to
the resulting distributions. All p-values can be found in the supplementary
material.

Implementation details.  All experiments where conduced using Nvidia
Tesla-V100 GPUs. The experiments were implemented in Python 3.7.9 using
PyTorch 1.8.0 and segmentation-models-pytorch [31]. The source code as well as
all of the raw data is available at
https://anonymous.4open.science/r/SegmentationConsistencyTraining-84EB

The augmentation method used both for the baseline and as part of Consistency
Training was implemented using the albumentations library [7], and consisted
of the following transformations: RandomRotate90, GaussNoise,
ImageCompression, OpticalDistortion and ColorJitter. For the regular
augmentation baseline, the augmentation probability was set to $0.5$, in which
case all of the aforementioned transformations were applied. All
hyperparameters can be found in the supplementary material.

###  4.2 Out of Distribution Generalization

Table 2 shows the mean mIoUs for models trained with and without data
augmentation, and models trained with Consistency Training. Comparing
Consistency Training and conventional data augmentation for each model,
statistical significance was achieved for all models except the TriUnet on the
Etis-LaribDB dataset, for the FPN and Unet on the CVC-ClinicDB dataset, and
for the Unet on the EndoCV2020 dataset after an independent-sample t-test.
When comparing across all tested models, Consistency Training improves
generalization by a statistically significant margin (p<0.01) on all OOD
datasets over conventional augmentation after a Mann-Whitney U-test. A bar-
plot comparing the improvement due to Consistency Training and conventional
data augmentation is shown in Figure 4. This shows that Consistency Training
can be considered a more generalizable alternative to data augmentation.

Table 2: Mean IoUs for training methods, precision truncated to 99% confidence. Consistency training entries with greater performance than conventional augmentation are highlighted in bold. If they are better by a statistically significant margin (p>0.99) after an independent sample two-sided t-test, they are also marked with a "*". Model | No Augmentation |  Vanilla Augmentation |  Consistency Training
---|---|---|---
Kvasir-SEG (In-Distribution)
DeepLabV3+ | 0.822 |  0.850 |  0.852
FPN | 0.822 |  0.853 |  0.852
TriUnet | 0.817 |  0.841 |  0.845
Unet | 0.828 |  0.851 |  0.851
Etis-LaribDB (Out of Distribution)
DeepLabV3+ | 0.417 |  0.472 |  0.505*
FPN | 0.404 |  0.440 |  0.475*
TriUnet | 0.309 |  0.410 |  0.434
Unet | 0.403 |  0.447 |  0.481*
CVC-ClinicDB (Out of Distribution)
DeepLabV3+ | 0.684 |  0.733 |  0.740
FPN | 0.675 |  0.715 |  0.727*
TriUnet | 0.623 |  0.684 |  0.696
Unet | 0.679 |  0.717 |  0.730*
EndoCV2020 (Out of Distribution)
DeepLabV3+ | 0.608 |  0.676 |  0.676
FPN | 0.600 |  0.662 |  0.673
TriUnet | 0.577 |  0.667 |  0.684
Unet | 0.598 |  0.660 |  0.676*
Figure 4: Improvements due Consistency Training and Data Augmentation as a
percentage the mean mIoU without augmentation across datasets.

##  5 Discussion and Conclusion

In this paper, we introduced Segmentation Consistency Training, a novel
training procedure for segmentation which explicitly optimizes for consistent
behaviour when an input subjected to augmentation. We showed that this
improves OOD generalization by a statistically significant amount across
several models when compared to conventional data augmentation. Moreover, we
show that Consistency Training mitigates underspecification to a greater
extent than data augmentation by analyzing performance variability.

###  5.1 Limitations

The batch size was kept constant across all experiments performed in this
paper. However, as it can be argued that since Consistency Training implicitly
increases the batch size, the experiments should ideally be repeated across a
range of batch sizes.

Moreover, the experiments were only performed with one specific augmentation
strategy. As it may be the case that the differences would be less significant
if a more sophisticated strategy was used, repeating the experiment with a
range of different augmentation functions and hyperparameter values is
warranted.

As the experiments were only performed on polyp datasets, it can also be
argued that it is uncertain whether Consistency Training has similar impacts
on other segmentation tasks.

Finally, a larger number of samples should ideally have been collected across
a wider diversity of model architectures. Increasing the granularity of the
findings by other means, for instance by using a greater number of OOD
datasets or designing parameterized stress-tests may also be warranted in
order to develop a more thorough understanding of the impact of our methods.

###  5.2 Future Work

We plan to investigate a number of potential improvements of this framework.
Consistency was for instance in this paper quantified as the symmetric
difference between the expected change in the output due to augmentation and
the actual change due to augmentation. This is largely agnostic to the
augmentation being performed. However, it may be beneficial to take the nature
of these augmentations into account. If the image is subjected to a 90 degree
rotation, for instance, the prediction would following the notion of
consistency as used in this work be considered perfectly consistent so long as
the pixels corresponding to the polyps are rotated, and the incorrectly
classified pixels remain unchanged. However, if the model instead learns to
rotate all of the pixels - even those that are incorrectly classified - it may
learn a more accurate representation of what constitutes consistent behavior
under rotation. That means, instead of expressing inconsistency as in eq. 3,
one can adjust the expected change term $a\oplus y$ to
$\hat{y}\oplus\epsilon(\hat{y})$ such that also incorrect predictions can be
considered consistent so long as they change in accordance to the nature of
the perturbation model $\epsilon(\cdot)$. The resulting loss function can then
be expressed as:

$\overline{\mathcal{C}}(\hat{y},\hat{a})=\sum\frac{\Theta(\hat{y},\hat{a},\hat{y},\epsilon(\hat{y}))}{\bigcup(\hat{y},\hat{a},\epsilon(\hat{y}))}$

Which is equivalent to:

$\overline{\mathcal{C}}(\hat{y},\hat{a})=\sum\frac{\Theta(\hat{y},\hat{a},\epsilon(\hat{y}))}{\bigcup(\hat{y},\hat{a},\epsilon(\hat{y}))}$

This also has the advantage of being independent of the labels themselves.
This may alleviate complications that may arise as a consequence of poor
and/or incomplete labeling which would otherwise affect what the models learn
to associate with consistent behaviour.

Repeating the experiments in this paper on a multitude of other segmentation
tasks, for instance scene segmentation for autonomous vehicles, is also
warranted. Evaluating Consistency Training through the use of stress-tests,
for instance by augmenting datasets with a disjoint set of transformations as
those used for training, may also provide some insights.

Further, one could investigate whether the consistency-training framework also
can be implemented in the context of classification, object detection, or
other applications of Deep Learning, and if similar improvements to
generalizability can be shown in other domains.

Finally, one may compare the learned features of models trained with
Consistency Training and the learned features of models trained
conventionally. This could for instance be achieved through the use of Grad-
CAM [27] or similar methods, and may be beneficial towards determining whether
the model has learned at least partial invariance to the given augmentations.

##  6 Acknowledgment

The research presented in this paper has benefited from the Experimental
Infrastructure for Exploration of Exascale Computing (eX3), which is
financially supported by the Research Council of Norway under contract 270053.

## References

  * [1] Sharib Ali et al.  “Assessing generalisability of deep learning-based polyp detection and segmentation methods through a computer vision challenge”  arXiv, 2022  DOI: 10.48550/ARXIV.2202.12031
  * [2] “EndoCV2020: 2nd International Workshop and Challenge on Computer Vision in Endoscopy”  Iowa, USA: CEUR Workshop Proceedings, 2020  URL: http://ceur-ws.org/Vol-2595/
  * [3] “Proceedings of the 3rd International Workshop and Challenge on Computer Vision in Endoscopy (EndoCV 2021) co-located with with the 17th IEEE International Symposium on Biomedical Imaging (ISBI 2021)”
  * [4] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani and David Lopez-Paz  “Invariant Risk Minimization”  arXiv, 2019  DOI: 10.48550/ARXIV.1907.02893
  * [5] Jorge Bernal et al.  “WM-DOVA maps for accurate polyp highlighting in colonoscopy: Validation vs. saliency maps from physicians”  In _Computerized Medical Imaging and Graphics_ 43 Elsevier, 2015, pp. 99–111  DOI: http://dx.doi.org/10.1016/j.compmedimag.2015.02.007
  * [6] Battista Biggio et al.  “Evasion Attacks against Machine Learning at Test Time”  In _Lecture Notes in Computer Science_ Springer Berlin Heidelberg, 2013, pp. 387–402  DOI: 10.1007/978-3-642-40994-3_25
  * [7] A. Buslaev et al.  “Albumentations: fast and flexible image augmentations”  In _ArXiv e-prints_ , 2018  URL: https://albumentations.ai/
  * [8] Liang-Chieh Chen, George Papandreou, Florian Schroff and Hartwig Adam  “Rethinking Atrous Convolution for Semantic Image Segmentation”  arXiv, 2017  DOI: 10.48550/ARXIV.1706.05587
  * [9] Alexander D’Amour et al.  “Underspecification Presents Challenges for Credibility in Modern Machine Learning”  arXiv, 2020  DOI: 10.48550/ARXIV.2011.03395
  * [10] Logan Engstrom et al.  “Exploring the Landscape of Spatial Robustness”  arXiv, 2017  DOI: 10.48550/ARXIV.1712.02779
  * [11] Robert Geirhos et al.  “Shortcut learning in deep neural networks”  In _Nature Machine Intelligence_ 2.11 Springer ScienceBusiness Media LLC, 2020, pp. 665–673  DOI: 10.1038/s42256-020-00257-z
  * [12] Tejas Gokhale et al.  “Generalized but not Robust? Comparing the Effects of Data Modification Methods on Out-of-Domain Generalization and Adversarial Robustness”  arXiv, 2022  DOI: 10.48550/ARXIV.2203.07653
  * [13] Ian Goodfellow, Yoshua Bengio and Aaron Courville  “Deep Learning” http://www.deeplearningbook.org MIT Press, 2016
  * [14] Ran Gu et al.  “Domain Composition and Attention for Unseen-Domain Generalizable Medical Image Segmentation”  In _Medical Image Computing and Computer Assisted Intervention – MICCAI 2021_ Cham: Springer International Publishing, 2021, pp. 241–250  DOI: https://doi.org/10.1007/978-3-030-87199-4_23
  * [15] Dan Hendrycks and Thomas Dietterich  “Benchmarking Neural Network Robustness to Common Corruptions and Perturbations”, 2019  arXiv:1903.12261 [cs.LG]
  * [16] Dan Hendrycks et al.  “AugMix: A Simple Data Processing Method to Improve Robustness and Uncertainty”  arXiv, 2019  DOI: 10.48550/ARXIV.1912.02781
  * [17] Ayoung Honga et al.  “Deep Learning Model Generalization with Ensemble in Endoscopic Images”  In _Proceedings of the 3rd International Workshop and Challenge on Computer Vision in Endoscopy (EndoCV 2021) co-located with with the 17th IEEE International Symposium on Biomedical Imaging (ISBI 2021)_ , 2021, pp. 80–89  URL: http://ceur-ws.org/Vol-2886/paper8.pdf
  * [18] Hossein Hosseini, Baicen Xiao and Radha Poovendran  “Google’s Cloud Vision API Is Not Robust To Noise”, 2017  arXiv:1704.05051 [cs.CV]
  * [19] Andrew Ilyas et al.  “Adversarial Examples Are Not Bugs, They Are Features”  arXiv, 2019  DOI: 10.48550/ARXIV.1905.02175
  * [20] Debesh Jha et al.  “Kvasir-SEG: A Segmented Polyp Dataset”  arXiv, 2019  DOI: 10.48550/ARXIV.1911.07069
  * [21] Jacob Kauffmann, Lukas Ruff, Grégoire Montavon and Klaus-Robert Müller  “The Clever Hans Effect in Anomaly Detection”, 2020  arXiv:2006.10609 [cs.LG]
  * [22] Tsung-Yi Lin et al.  “Feature Pyramid Networks for Object Detection”  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017
  * [23] Alexander Robey, Hamed Hassani and George J. Pappas  “Model-Based Robust Deep Learning: Generalizing to Natural, Out-of-Distribution Data”, 2020  arXiv:2005.10247 [cs.LG]
  * [24] Olaf Ronneberger, Philipp Fischer and Thomas Brox  “U-Net: Convolutional Networks for Biomedical Image Segmentation”  arXiv, 2015  DOI: 10.48550/ARXIV.1505.04597
  * [25] Veit Sandfort, Ke Yan, Perry Pickhardt and Ronald Summers  “Data augmentation using generative adversarial networks (CycleGAN) to improve generalizability in CT segmentation tasks”  In _Scientific Reports_ 9, 2019  DOI: 10.1038/s41598-019-52737-x
  * [26] Bernhard Schölkopf  “Causality for Machine Learning”  arXiv, 2019  DOI: 10.48550/ARXIV.1911.10500
  * [27] Ramprasaath R. Selvaraju et al.  “Grad-CAM: Visual Explanations from Deep Networks via Gradient-Based Localization”  In _International Journal of Computer Vision_ 128.2 Springer ScienceBusiness Media LLC, 2019, pp. 336–359  DOI: 10.1007/s11263-019-01228-7
  * [28] Juan Silva et al.  “Toward embedded detection of polyps in wce images for early diagnosis of colorectal cancer”  In _International journal of computer assisted radiology and surgery_ 9.2 Springer, 2014, pp. 283–293  DOI: https://doi.org/10.1007/s11548-013-0926-3
  * [29] Vajira Thambawita et al.  “An Extensive Study on Cross-Dataset Bias and Evaluation Metrics Interpretation for Machine Learning Applied to Gastrointestinal Tract Abnormality Classification”  In _ACM Trans. Comput. Healthcare_ 1.3 New York, NY, USA: Association for Computing Machinery, 2020  DOI: 10.1145/3386295
  * [30] Vajira Thambawita, Steven A. Hicks, Pål Halvorsen and Michael A. Riegler  “DivergentNets: Medical Image Segmentation by Network Ensemble”  In _Proceedings of the 3rd International Workshop and Challenge on Computer Vision in Endoscopy (EndoCV 2021) co-located with with the 17th IEEE International Symposium on Biomedical Imaging (ISBI 2021)_ , 2021, pp. 27–38  URL: https://arxiv.org/abs/2107.00283
  * [31] Pavel Yakubovskiy  “Segmentation Models Pytorch”  In _GitHub repository_ GitHub, https://github.com/qubvel/segmentation_models.pytorch, 2020

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes] . See fig. 4 and table 2.

    2. (b)

Did you describe the limitations of your work? [Yes] . See section 5.1

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [N/A]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
. Code and data was made available in the form of a Github repository.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes] . See supplementary material.

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes] . See fig. 4. If the improvement error bars
are unsatisfactory, the raw data is also available on the github repository.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] . This was
discussed in Section 4.1 and in the acknowledgment.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes] . See
References list.

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes] . The code can be found on the github repository.

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]