Kempe equivalence of 4-colourings of some plane triangulations

Abstract

Let $G_n$, where $n⩾5$, be a simple plane triangulation which has $2$ non-adjacent vertices of degree $n$ (called \textit{poles} of $G_n$) and $2n$ vertices of degree~$5$. A set of Kempe equivalent $4$-colourings of $G_n$ is called a \textit{Kempe class}. The number of Kempe classes of $G_n$ is enumerated. In particular it is shown that there is at least $\lfloor \frac{n}{6}\rfloor$ Kempe classes of $G_n$. We say that $4$-colourings $A,B$ of $G_n$ are \textit{equal} if there exists a permutation~$P$ of the set of colours such that $A=P\circ B$. Otherwise, $A$, $B$ are \textit{different}. The number of different $4$-colourings of $G_n$ is enumerated. Suppose that $H_n=G_n-b$, where $b$ is a pole of $G_n$. We prove that all $4$-colourings of $H_n$ are Kempe equivalent up to $\lfloor \frac{13n}{2}\rfloor$ Kempe changes. %$3n$ ($\lfloor \frac{9n}{2}\rfloor$ and $\lfloor \frac{13n}{2}\rfloor$) Kempe changes, for $n\equiv 0(mod3)$ ($n\equiv 2(mod3)$ and $n\equiv 1(mod3)$, respectively).

26 pages, 10 figures