%% filename: amsart-template.tex
%% American Mathematical Society
%% AMS-LaTeX v.2 template for use with amsart
%% ====================================================================

\documentclass{amsart}

\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{backgrounds}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

\begin{document}

\title{Three-Colour Restrictions for Nested Tire Graphs}

%    author one information
\author{Eric Bauerfeld}
\address{}
\curraddr{}
\email{}
\thanks{}

\subjclass[2010]{Primary }

\keywords{plane graph, triangulation, plane depth, level edge, dual graph, tire graph}

\date{}

\dedicatory{}

\begin{abstract}
We study three-colour boundary restrictions suggested by the nested
tire decomposition of a plane triangulation.  A level source induces a
rooted tree of tire treads, and global colouring questions factor
through local tread colourings together with compatibility along nested
boundary cycles.  We formulate a level-cycle three-colour restriction,
exhibit counterexamples to two overly strong forms, and record
exhaustive evidence for a surviving source-dependent conjecture.  We
also introduce seam language for minimum Four Colour Theorem
counterexamples in the tire-tree framework.
\end{abstract}

\maketitle

\section{Introduction}

A classical theorem of Tait recasts the Four Colour Theorem in dual,
edge-colouring terms: a plane triangulation $G$ is properly $4$-vertex-colourable
if and only if its dual cubic graph $G'$ is properly $3$-edge-colourable. Thus a
minimal counterexample to the Four Colour Theorem -- a smallest triangulation
admitting no proper $4$-colouring -- corresponds to a smallest cubic plane graph
admitting no proper $3$-edge-colouring.

The structural study of such a minimal counterexample is the
overarching motivation for the present line of work.  The companion
decomposition paper~\cite{bauerfeld-nested-tire-decompositions}
establishes the foundational vocabulary --- level sources, dual depth,
tire graphs, medial tire graphs, and tire-tree decompositions --- on
which this paper builds.  The companion dual paper
\cite{bauerfeld-nested-tire-duals} develops nested-cycle structure
theorems and chain-pigeonhole conjectures for tire annular subgraphs
of $G'$.

\paragraph{Related work.}
The structural object underlying this programme --- the set of
proper $4$-colourings of a boundary cycle that extend to a colouring
of a bounded planar region --- is classical.  Birkhoff's reducibility
analysis of the diamond configuration~\cite{birkhoff-reducibility} is
the earliest instance of computing such extension sets to attack the
Four Colour Theorem; the chromatic polynomial framework of Birkhoff
and Lewis~\cite{birkhoff-lewis-chromatic} systematised the counting.
Tutte studied how the chromatic polynomial of a rooted planar
triangulation decomposes along its outer
boundary~\cite{tutte-chromatic-sums-1973} and developed an algebraic
theory of graph colourings organised around separating
subgraphs~\cite{tutte-algebraic-colorings, tutte-four-colour-conjecture}.
The most recent and structurally closest parallel is Dvo\v{r}\'ak
and Lidick\'y's analysis of \emph{coloring count
cones}~\cite{dvorak-lidicky-cones}, which characterises the possible
boundary-extension functions on a fixed outer cycle of a
near-triangulation.  The Heesch--Appel--Haken
approach~\cite{heesch-untersuchungen, robertson-sanders-seymour-thomas}
also uses boundary-extension reasoning, but case-by-case on a finite
unavoidable set of local configurations rather than as part of a
global structural induction.

The tire-tree decomposition used here differs from each of
these in shape rather than ingredients.  Birkhoff, Tutte, and
Dvo\v{r}\'ak--Lidick\'y all study \emph{one} boundary; Heesch and
the cleaned-up Appel--Haken proof~\cite{robertson-sanders-seymour-thomas}
study a finite collection of local boundaries.  The present framework
organises the entire triangulation into a hierarchy of annular
regions glued along level cycles, and asks whether boundary-extension
constraints compose compatibly up the hierarchy.  To the authors'
knowledge, no prior work on the Four Colour Theorem has been
organised around a global nested-cycle decomposition of this kind.

\section{Background from nested tire decompositions}

We use the terminology and structural results of~\cite{bauerfeld-nested-tire-decompositions}.  In particular, a level source induces levels in a plane maximal planar graph, the depth-$d$ inner-dual components determine tire graphs, and the resulting tire treads form a rooted tire tree $\mathcal{T}(G,S)$.  For a tread $T$, we write $B_{\mathrm{out}}^{(T)}$ and $B_{\mathrm{in}}^{(T)}$ for its outer and inner boundary data, $O^{(T)}$ for its inner outerplanar graph, and $G_T$ for the triangulated disk on the descendant side of $B_{\mathrm{out}}^{(T)}$.  The base paper also proves that each tire tread has an outerplanar inner dual and that global colouring questions factor through local tread colourings together with compatibility along parent-child interfaces.

\section{Single-tire colouring transfer}

\begin{theorem}[Tait correspondence: 4-colorings of a tire vs 3-edge-colorings of its inner dual]
\label{thm:tait-tire}
Let $T = (B_{\mathrm{out}}, O, E_{\mathrm{ann}})$ be a tire graph
(viewed as an annular triangulation of its tire tread $R$) and let
$\Gamma$ be its outerplanar inner dual, as supplied by
\cite{bauerfeld-nested-tire-decompositions}.  Then
\[
   \#\bigl\{\text{proper $4$-vertex-colorings of } T\bigr\} \big/ |S_4|
   \;=\;
   \#\bigl\{\text{proper $3$-edge-colorings of } \Gamma\bigr\} \big/ |S_3|.
\]
That is, the number of $4$-vertex-colorings of $T$ up to permutation
of the colour set $\{0, 1, 2, 3\}$ equals the number of
$3$-edge-colorings of $\Gamma$ up to permutation of the colour set
$\{1, 2, 3\}$.
\end{theorem}

\begin{proof}
The argument is the classical Tait correspondence
\cite{tait-original} adapted to the annular triangulation $T$.
Encode the four colours of a proper $4$-vertex-coloring $c \colon
V(T) \to \mathbb{Z}_2 \times \mathbb{Z}_2$.  For each interior
annular edge $e$ of $T$ (whose two incident faces both lie in
$F_{\mathrm{ann}}$, contributing a $\Gamma$-edge $e^*$), set
\[
    \chi^*(e^*) \;:=\; c(u) + c(v) \in \mathbb{Z}_2 \times \mathbb{Z}_2,
    \qquad \text{where } u, v \text{ are the endpoints of } e.
\]
Since $c(u) \ne c(v)$, we have $\chi^*(e^*) \ne 00$, so $\chi^*$
takes values in $\{01, 10, 11\}$, which we identify with the
$3$-edge-coloring palette $\{1, 2, 3\}$.

\emph{Properness.}  At each $\Gamma$-vertex $d_f$ corresponding to
an annular triangle $f = \{u, v, w\}$, the three incident
$\Gamma$-edges (one per cycle-edge of $f$) carry colours
$c(u) + c(v),\; c(v) + c(w),\; c(u) + c(w)$.  These three elements
of $\mathbb{Z}_2 \times \mathbb{Z}_2$ sum to $0$ and are pairwise
distinct (their pairwise differences are
$c(u) - c(w),\; c(v) - c(u),\; c(w) - c(v)$, each nonzero), so
they form a permutation of $\{01, 10, 11\}$ --- a proper edge
colouring at $d_f$.

\emph{Surjectivity onto cosets.}  Given a proper $3$-edge-coloring
$\chi^*$ of $\Gamma$, the equation $c(u) + c(v) = \chi^*(e^*)$
admits exactly $|\mathbb{Z}_2 \times \mathbb{Z}_2| = 4$ solutions
$c \colon V(T) \to \mathbb{Z}_2 \times \mathbb{Z}_2$ (a global
translation is the only freedom).  Hence the map $c \mapsto
\chi^*$ is $4$-to-$1$.

\emph{Count.}  Therefore $\#\{\text{4-colorings of } T\} = 4 \cdot
\#\{\text{3-edge-colorings of } \Gamma\}$.  Dividing by $|S_4|
= 24$ on the left and $|S_3| = 6$ on the right (since $S_4$ acts
faithfully on the $4$-colorings and $S_3$ on the $3$-edge-colorings,
and the $4$-to-$1$ map respects the $S_4/S_3 \cong S_3$ quotient
via the natural surjection $S_4 \twoheadrightarrow S_3$) gives the
stated equality.
\end{proof}

\begin{remark}
\label{rem:count-general-outerplanar}
Theorem~\ref{thm:tait-tire} reduces the $4$-colouring count of a
tire to the $3$-edge-coloring count of its outerplanar inner dual
$\Gamma$.  For the cycle case $\Gamma \cong C_{\mu+\nu}$ (the spoke-only
case described in \cite{bauerfeld-nested-tire-decompositions}), the cycle
chromatic polynomial at $3$ colours gives
$2^{\mu+\nu} + 2 (-1)^{\mu+\nu}$.  For an inner dual with one or more
non-crossing chords, the count depends on the chord structure, not just
on the pair (number of vertices, number of chords): two outerplanar
graphs with the same number of vertices and number of chords can have
different proper
$3$-edge-coloring counts depending on how the chords are arranged
(nested, sequential, sharing vertices, etc.).  Every such count
can nevertheless be computed in linear time by tree-decomposition
methods, since outerplanar graphs have treewidth at most $2$ and
the edge-chromatic polynomial admits a deletion--contraction
recursion that respects the cycle-plus-chord structure.
\end{remark}

\begin{definition}[Boundary-state chromatic transfer]
\label{def:boundary-state-transfer}
Let $T = (B_{\mathrm{out}}, O, E_{\mathrm{ann}})$ be a tire graph.
Choose a cut along one annular edge if both boundaries are
non-degenerate; in the degenerate case make no cut.  The tread becomes
a triangulated disk $\widetilde R$.  Let
\[
   f_1, f_2, \ldots, f_m
\]
be any shelling order of the triangular faces of $\widetilde R$, i.e.\
an order in which each initial union
$\widetilde R_i := f_1 \cup \cdots \cup f_i$ is a disk.  Such an order
is obtained by taking an outerplanar embedding of the inner dual
$\Gamma$ from \cite{bauerfeld-nested-tire-decompositions} and repeatedly
removing an outer-face ear.

For each $i$, let $A_i$ be the \emph{frontier}: the vertices of
$T$ incident to at least one processed face in $\widetilde R_i$ and to
at least one still-unprocessed constraint, where the unprocessed
constraints are the remaining annular faces together with any edge of
$O$ not yet tested by the transfer.  A \emph{boundary state} on $A_i$
is a partition $\pi$ of $A_i$ into colour classes, subject to the
condition that adjacent vertices of $T[A_i]$ lie in distinct blocks.
We write $r(\pi)$ for the number of blocks of $\pi$.
\end{definition}

\begin{theorem}[Chromatic polynomial of a tire by frontier transfer]
\label{thm:tire-chromatic-polynomial-transfer}
For every tire graph $T$, the chromatic polynomial $P_T(q)$ is
computed by the following boundary-state dynamic program.

Initialize the table at $i=0$ with the empty frontier state of weight
$1$.  When the next triangular face
$f_i = \{x,y,z\}$ is attached, pass from states on $A_{i-1}$ to states
on $A_i$ as follows.
\begin{enumerate}
\item[(1)] Introduce any vertices of $f_i$ not already present in
          $A_{i-1}$, assigning each such vertex either to an existing
          colour block not containing one of its already-coloured
          neighbours, or to a new block.
\item[(2)] Reject every assignment in which two adjacent vertices of
          the triangle $f_i$ lie in the same block.  Also reject every
          assignment in which an edge of $O$ whose two endpoints have
          now both appeared for the first time as a tested pair has
          both endpoints in the same block.  Thus chords and bridges of
          the inner outerplanar graph are enforced exactly when their
          second endpoint becomes visible to the transfer.
\item[(3)] Delete from the state every vertex no longer incident to an
          unprocessed constraint.  If deleting a vertex removes the last
          representative of its colour block from the frontier, multiply
          that transition by $1$; the colour has already been chosen.
\item[(4)] If a new vertex is assigned to a new colour block while the
          current frontier state has $r$ colour blocks, multiply that
          transition by $q-r$.  If several new colour blocks are created
          in the same triangle, the factors are
          $(q-r)(q-r-1)\cdots$ in the order of creation.
\end{enumerate}
After $f_m$ is processed, the frontier is empty.  The single remaining
weight is $P_T(q)$.
\end{theorem}

\begin{proof}
The construction is the standard transfer for the chromatic polynomial,
specialized to the tire shelling.  The frontier state records exactly
the equality pattern among colours that can still affect unprocessed
faces.  Since colour names are irrelevant to the chromatic polynomial,
states are quotiented by the natural action of the symmetric group on
the colour set; a state with $r$ visible colour blocks can be extended
by a genuinely new colour in $q-r$ ways.

Each transition accounts for all proper colourings of the enlarged
processed disk $\widetilde R_i$ that restrict to the resulting frontier
state, and accounts for none that violate an edge of the newly attached
triangle or untested edge of $O$.  Vertices removed from the frontier
have no future incident unprocessed constraint, so their actual colour
names can no longer influence compatibility and may be forgotten.
Induction on $i$ therefore shows
that the table after step $i$ is precisely the orbit-count generating
function for proper colourings of $\widetilde R_i$ by frontier state.
At $i=m$ no vertices remain active, so the accumulated weight counts all
proper colourings of $T$.  Because the weights are polynomials in $q$,
this count is the full chromatic polynomial.
\end{proof}

\begin{remark}[Spoke-only transfer matrix]
\label{rem:spoke-only-chromatic-transfer}
In the spoke-only case with both boundaries simple cycles, the method
has a particularly small form.  Cut the annulus along one spoke and
walk around the resulting strip.  Each step adds one triangle sharing
an edge with the previous processed strip, so the frontier consists of
two or three consecutive boundary vertices.  Up to colour permutation
there are only the possible equality patterns among those active
vertices, with adjacent vertices required to be distinct.  The
chromatic polynomial is therefore the trace of a finite transfer matrix
whose entries are polynomials in $q$; the matrix depends only on the
local triangle type encountered while walking around the tread.  Chords
or cut-vertices of $O$ enlarge the frontier only at the corresponding
outerplanar ears, and are handled by the same state rule of
Theorem~\ref{thm:tire-chromatic-polynomial-transfer}.
\end{remark}

\begin{remark}[Motivation for level-cycle restrictions]
\label{rem:level-cycle-motivation}
The tire-tree decomposition reduces global colouring questions to local
choices on treads together with compatibility along nested boundary
cycles.  Without further structure, the number of boundary colour states
can grow quickly as one descends the tree: each seam or level cycle may
in principle carry any proper restriction of a $4$-colouring.  The
following restriction is meant to test whether this state space can be
compressed.  If level cycles can always be made to omit one colour, then
each such interface behaves like a three-colour boundary object, while
still allowing different cycles to omit different colours.  This would
not by itself solve the gluing problem, but it would give a simpler
target class of boundary states for arguments about nested tire trees.
\end{remark}

\begin{definition}[Level-cycle three-colour restriction]
\label{def:level-cycle-three-colour-restriction}
Let $G$ be a maximal planar graph, let $S \subseteq V(G)$ be a level
source, and let $c \colon V(G) \to \{1,2,3,4\}$ be a proper
$4$-vertex-colouring of $G$.  We say that $c$ has the
\emph{level-cycle three-colour restriction} with respect to $S$ if,
for every level $d \geq 0$ and every simple cycle
$C \subseteq G[L_d]$, the colour set used on $C$ has size at most
three:
\[
    |c(V(C))| \leq 3.
\]
Equivalently, every simple cycle contained in a single level omits at
least one of the four colours.  The omitted colour may depend on the
cycle; in particular, distinct cycles in the same level, the same tire
tread, or the same inner outerplanar component are not required to
omit the same colour.
\end{definition}

\begin{conjecture}[False universal-source form]
\label{conj:false-universal-level-cycle-three-colour}
Let $G$ be a maximal planar graph and let $S \subseteq V(G)$ be any
level source.  Then $G$ admits a proper $4$-vertex-colouring with the
level-cycle three-colour restriction with respect to $S$.
\end{conjecture}

\begin{figure}[htbp]
\centering
\includegraphics[width=0.78\textwidth]{fig_universal_level_cycle_counterexample.png}
\caption{The $8$-vertex counterexample to the universal-source form.
With source $S=\{7\}$, the level cycle $(3,4,5,8)$ lies in $L_2$ and
forces all four colours in every proper $4$-vertex-colouring.}
\label{fig:universal-level-cycle-counterexample}
\end{figure}

\begin{example}[Counterexample to Conjecture~\ref{conj:false-universal-level-cycle-three-colour}]
\label{ex:universal-level-cycle-counterexample}
Let $G$ be the maximal planar graph on vertex set
$\{1,2,3,4,5,6,7,8\}$ with edge set
\[
\begin{aligned}
E(G)=\{&
12,13,14,15,16,17,23,26,27,34,35,36,38,\\
&45,56,58,67,68\}.
\end{aligned}
\]
Here $ij$ denotes the edge $\{i,j\}$.
Take the vertex source $S=\{7\}$.  The corresponding levels are
\[
L_0=\{7\},\qquad L_1=\{1,2,6\},\qquad
L_2=\{3,4,5,8\}.
\]
Inside $G[L_2]$ the vertices $(3,4,5,8)$ form a simple cycle.  In
every proper $4$-vertex-colouring of $G$, these four vertices receive
four distinct colours.  The edges $34$, $45$, $58$, $38$, and $35$
force all pairs among $\{3,4,5,8\}$ except possibly $\{4,8\}$ to have
distinct colours.  If $4$ and $8$ had the same colour, then vertex $6$,
which is adjacent to $3$, $5$, and $8$, would have to use the fourth
colour; but vertex $1$ is adjacent to $3$, $4$, $5$, and $6$, and
would then be adjacent to all four colours, impossible in a proper
$4$-colouring.  Hence $4$ and $8$ also have distinct colours, so the
level cycle $(3,4,5,8)$ uses all four colours in every proper
$4$-colouring of $G$.  Therefore no proper $4$-colouring has the
level-cycle three-colour restriction with respect to $S=\{7\}$.
\end{example}

\subsection*{An inner-boundary refinement}

The level-cycle restriction constrains \emph{every} simple cycle in
every level.  For the tire-tree program, the cycles that actually carry
boundary state are fewer: each tire transfers colour information across
its tread between its two boundaries, so it is the tire
\emph{inner boundaries} $B_{\mathrm{in}}^{(T)}$ --- not all level cycles
--- that one wishes to compress.  This motivates a restriction stated
directly in the objects of the decomposition.

\begin{definition}[Tire inner-boundary three-colour restriction]
\label{def:tire-inner-boundary-three-colour}
Let $G$ be a maximal planar graph, let $v_0 \in V(G)$ be a vertex source
on the outer face of $\Pi_G$, and let $c \colon V(G) \to \{1,2,3,4\}$ be
a proper $4$-vertex-colouring of $G$.  We say $c$ has the \emph{tire
inner-boundary three-colour restriction} with respect to
$\mathcal{T}(G, \{v_0\})$ if every tire tread $T \in
\mathcal{T}(G, \{v_0\})$ satisfies
\[
    |c(V(B_{\mathrm{in}}^{(T)}))| \leq 3,
\]
i.e.\ the inner boundary of every tire omits at least one of the four
colours.  (A degenerate inner boundary is a single vertex and the
condition is then vacuous.)
\end{definition}

\begin{conjecture}[Tire inner-boundary three-colour conjecture]
\label{conj:tire-inner-boundary-three-colour}
Every maximal planar graph $G$ admits a vertex source $v_0 \in V(G)$ and
a proper $4$-vertex-colouring $c$ of $G$ such that $c$ has the tire
inner-boundary three-colour restriction with respect to
$\mathcal{T}(G, \{v_0\})$.
\end{conjecture}

\subsection*{A counterexample at $n=14$}

Conjecture~\ref{conj:tire-inner-boundary-three-colour} is in fact
false.  An exhaustive search over the triangulations enumerated by
\texttt{plantri} at $n=14$ encounters a graph $G^\star$ on $14$ vertices
and $36$ edges --- specifically, the graph at index $263993$ in the
\texttt{plantri} enumeration --- for which no vertex source admits any
witness.

\begin{example}[Counterexample to Conjecture~\ref{conj:tire-inner-boundary-three-colour}]
\label{ex:inner-boundary-counterexample}
Let $G^\star$ be the maximal planar graph with vertex set
$\{1,2,\dots,14\}$ and edge set
\begin{align*}
E(G^\star) = \{
  & 12, 13, 14, 15, 16, 17, 18, \\
  & 23, 24, 26, 28, 29, 2\,10, \\
  & 34, 45, 46, 4\,10, 56, 67, 69, 6\,10, \\
  & 78, 79, 7\,11, 7\,12, 7\,13, \\
  & 89, 8\,12, 8\,13, 8\,14, \\
  & 9\,11, 9\,12, 9\,14, \\
  & 11\,12, 12\,13, 12\,14
\}.
\end{align*}
The graph $G^\star$ is a $3$-connected (but not $5$-connected) planar
triangulation with degree sequence
$(7,7,7,7,7,7,6,6,3,3,3,3,3,3)$ and exactly $96$ proper $4$-vertex
colourings.  For \emph{every} choice of vertex source
$v_0 \in V(G^\star)$, each of the $96$ proper $4$-colourings of
$G^\star$ has some tire whose inner boundary uses all four colours.
A planar embedding is shown in
Figure~\ref{fig:inner-boundary-counterexample}.
\end{example}

\begin{figure}[ht]
\centering
\includegraphics[width=0.78\textwidth]{fig_inner_boundary_counterexample}
\caption{The $14$-vertex counterexample $G^\star$ to
Conjecture~\ref{conj:tire-inner-boundary-three-colour} in a planar
embedding.  The six degree-$3$ vertices split into two triples,
$\{3,5,10\}$ each adjacent to a triangle in the
core $\{1,2,4,6\}$, and $\{11,13,14\}$ each adjacent to a triangle in
the core $\{7,8,9,12\}$; the two cores are joined by the edges
$17,28,69$ together with $12$.}
\label{fig:inner-boundary-counterexample}
\end{figure}

The failure was verified by enumerating, for each of the $14$ vertex
sources, all $96$ proper $4$-colourings of $G^\star$ and computing the
inner boundary $V(B_{\mathrm{in}}^{(T)})$ of every tire $T$ as the
level-$(d+1)$ vertices of the corresponding depth-$d$ dual component.
Each source has exactly two non-degenerate inner boundaries
(size $\geq 4$), and every proper $4$-colouring assigns all four
colours to at least one of them.

The graph $G^\star$ does not refute
Conjecture~\ref{conj:level-cycle-three-colour}: the vertex source
$v_0 = 10$ admits a proper $4$-colouring under which every simple level
cycle uses at most three colours.

\subsection*{The surviving level-cycle conjecture}

\begin{conjecture}[Level-cycle three-colour conjecture]
\label{conj:level-cycle-three-colour}
Let $G$ be a maximal planar graph.  Then there exists a level source
$S \subseteq V(G)$ such that $G$ admits a proper $4$-vertex-colouring
with the level-cycle three-colour restriction with respect to $S$.
\end{conjecture}

\subsection*{Enumeration for small $n$}

We exhaustively enumerated all plane triangulation isomorphism classes with
$4 \leq n \leq 13$ vertices and searched the vertex sources for each graph.
No counterexample to Conjecture~\ref{conj:level-cycle-three-colour} appeared
in this range.  Table~\ref{tab:level-cycle-three-colour-counts} records the
size of the search space and the number of triangulations that admit a
witness.

\begin{table}[ht]
\centering
\small
\setlength{\tabcolsep}{4pt}
\begin{tabular}{ccc}
$n$ & triangulations & with witness \\\hline
$4$  & $1$    & $1$ \\
$5$  & $1$    & $1$ \\
$6$  & $2$    & $2$ \\
$7$  & $5$    & $5$ \\
$8$  & $14$   & $14$ \\
$9$  & $50$   & $50$ \\
$10$ & $233$  & $233$ \\
$11$ & $1249$ & $1249$ \\
$12$ & $7595$ & $7595$ \\
$13$ & $49566$ & $49566$ \\
\end{tabular}
\caption{Exhaustive vertex-source search for the level-cycle three-colour conjecture on all triangulation isomorphism classes with $4 \leq n \leq 13$.  Every triangulation in this range admits at least one vertex source witnessing the conjecture.}
\label{tab:level-cycle-three-colour-counts}
\end{table}

We also tested the six dual triangulations of the Holton--McKay graphs,
which lie just beyond this census, and found witnesses in each case.

\subsection*{The $5$-connected slice at $n \leq 24$}

As a compact test above the full small-$n$ census, we also enumerated the
$5$-connected triangulations at $14 \leq n \leq 24$ with \texttt{plantri
-c5 -a}.  These are especially rigid triangulations, and the slice remains
small enough to check exhaustively.  Every graph in this slice admits a
vertex source witnessing Conjecture~\ref{conj:level-cycle-three-colour}.

\begin{table}[ht]
\centering
\small
\setlength{\tabcolsep}{4pt}
\begin{tabular}{ccc}
$n$ & $5$-connected triangulations & with witness \\\hline
$14$ & $1$ & $1$ \\
$15$ & $1$ & $1$ \\
$16$ & $3$ & $3$ \\
$17$ & $4$ & $4$ \\
$18$ & $12$ & $12$ \\
$19$ & $23$ & $23$ \\
$20$ & $71$ & $71$ \\
$21$ & $187$ & $187$ \\
$22$ & $627$ & $627$ \\
$23$ & $1970$ & $1970$ \\
$24$ & $6833$ & $6833$ \\
\end{tabular}
\caption{The $5$-connected triangulations at $14 \leq n \leq 24$ generated by
\texttt{plantri -c5 -a}.  All $9732$ graphs in this slice admit a vertex
source witnessing the level-cycle three-colour conjecture.}
\label{tab:level-cycle-three-colour-c5-14-16}
\end{table}

\begin{definition}[Seam]
\label{def:seam}
A \emph{seam} of a maximal planar graph $G$ is a simple cycle
$C \subset G$ such that, for some vertex $v_0 \in V(G)$, $C =
B_{\mathrm{out}}^{(T)}$ for some non-root tread $T$ in
$\mathcal{T}(G, \{v_0\})$.

By the tire-tree decomposition theorem of
\cite{bauerfeld-nested-tire-decompositions}, every seam $C$ separates
$G$ into:
\begin{itemize}
\item the \emph{seam interior} $G_T$, the triangulated disk on the
      $T$-descendant side of $C$;
\item the \emph{seam exterior} $G_C^{\mathrm{ext}} := G \setminus
      \mathrm{int}(G_T)$, the triangulated polygon with outer face
      bounded by $C$ on the side containing $v_0$;
\end{itemize}
both sharing $C$.  A seam is \emph{non-trivial} if both
$V(G_T) \setminus V(C)$ and $V(G_C^{\mathrm{ext}}) \setminus V(C)$ are
non-empty.

For any seam $C$ and either side $X \in \{G_T, G_C^{\mathrm{ext}}\}$,
write
\[
   \mathrm{Col}(X \mid C) \;:=\; \bigl\{\, c|_{V(C)} \;:\; c \text{ a
   proper $4$-colouring of } X \,\bigr\} \;\subseteq\; \{1,2,3,4\}^{V(C)}
\]
for the set of $C$-restricted $4$-colourings induced by $4$-colourings
of $X$ (each element is a proper $4$-colouring of the cycle $C$).
\end{definition}

\begin{definition}[Partial tire tree]
\label{def:partial-tire-tree}
Let $T_r$ be a tire tread in $\mathcal{T}(G, S)$ with outer boundary
cycle $C_{T_r} = B_{\mathrm{out}}^{(T_r)}$, and let $G_{T_r}$ be the
triangulated disk inside $C_{T_r}$ given by the tire-tree
decomposition theorem of~\cite{bauerfeld-nested-tire-decompositions}.
The \emph{partial tire
tree} with root $T_r$, written $G_{T_r}^{\circ}$, is the induced
subgraph of $G$ on the vertex set
$V(G_{T_r}) \setminus V(C_{T_r})$ ---
i.e.\ $G_{T_r}$ with the seam-cycle vertices removed.

Equivalently, $V(G_{T_r}^{\circ})$ is the set of vertices of $G$
strictly inside $C_{T_r}$ on the side away from the level source,
and $E(G_{T_r}^{\circ})$ consists of the edges of $G$ both of whose
endpoints lie in this strict interior.  The tree-of-tire-treads
structure of $G_{T_r}^{\circ}$ is the sub-tree of $\mathcal{T}(G, S)$
rooted at $T_r$, with $T_r$'s outer boundary peeled away.
\end{definition}

\begin{lemma}[Seam edges are shared by at most one other depth-$d$ seam]
\label{lem:seam-edge-shared}
Let $G$ be a maximal planar graph with single-vertex level source
$S = \{v_0\}$, fix $d \ge 1$, and let $e \in E(G)$ be an edge lying on
the seam $C_T = B_{\mathrm{out}}^{(T)}$ of some tire tread
$T \in \mathcal{T}(G, S)$ at depth $d$.  Then there is at most one
other tire tread $T' \in \mathcal{T}(G, S)$ at the same depth $d$ with
$e \in C_{T'}$.
\end{lemma}

\begin{proof}
By the child--face correspondence in the tire-tree construction of
\cite{bauerfeld-nested-tire-decompositions}, $C_T$ is the boundary cycle of a
bounded face of the parent's inner outerplanar graph $O^{(T_p)}$,
where $T_p \in \mathcal{T}(G, S)$ is the parent of $T$ at depth
$d - 1$.  The inner dual of a connected outerplanar graph is a tree,
so each edge of
$O^{(T_p)}$ lies on at most two of its bounded face cycles.  Hence
$e$ lies on at most one other bounded face cycle of $O^{(T_p)}$,
corresponding, by the same child--face bijection,
to at most one sibling of $T$ at depth $d$ whose seam contains $e$.
\end{proof}

\begin{conjecture}[Seam structure of minimum $4$CT counterexamples, sketch]
\label{conj:seam-counterexample}
Suppose the Four Colour Theorem fails: there exists a maximal planar
graph that is not $4$-colourable.  Let $G$ be a \emph{minimum} such
counterexample (with $|V(G)|$ minimal among non-$4$-colourable maximal
planar graphs).  Then:

\medskip

\noindent\emph{Restatement-of-classical content.}
\begin{itemize}
\item[(C1)] \emph{Bilateral colourability.}  For every non-trivial seam
            $C$ of $G$, both $\mathrm{Col}(G_T \mid C)$ and
            $\mathrm{Col}(G_C^{\mathrm{ext}} \mid C)$ are non-empty.
\item[(C2)] \emph{Bilateral incompatibility.}  For every non-trivial
            seam $C$,
            \[
               \mathrm{Col}(G_T \mid C) \;\cap\;
               \mathrm{Col}(G_C^{\mathrm{ext}} \mid C) \;=\; \emptyset.
            \]
\item[(C3)] \emph{Length lower bound (Birkhoff).}  Every non-trivial
            seam $C$ of $G$ has $|V(C)| \ge 6$.
\end{itemize}

(C1) and (C2) together restate ``$G$ is a counterexample whose every
internal cut by a seam splits into two colourable pieces with
incompatible boundary palettes''; (C1) follows from minimality applied
to each side after closing the polygonal outer face by a single apex,
(C2) from $G$ itself being non-$4$-colourable.  (C3) is Birkhoff's
internally-$6$-connected condition restated in the seam language.

\medskip

\noindent\emph{Substantive (speculative) content.}
\begin{itemize}
\item[(C4)] \emph{Innermost obstruction.}  There exists a vertex source
            $v_0 \in V(G)$ and a \emph{leaf} tread $T^* \in
            \mathcal{T}(G, \{v_0\})$ (a tread with no children in the
            tree-of-treads) such that:
            \begin{enumerate}
            \item[(i)] the seam interior $G_{T^*}$ is, up to plane
                  iso, one of a finite list of \emph{minimal seam
                  configurations}, characterized by their boundary
                  palette $\mathrm{Col}(G_{T^*} \mid C_{T^*})$ being a
                  specific proper subset of the proper $4$-colourings
                  of the cycle $C_{T^*}$;
            \item[(ii)] the path in $\mathcal{T}(G, \{v_0\})$ from the
                  root $T_0$ to $T^*$ is an \emph{obstruction chain}:
                  $\mathrm{Col}(G_T \mid C_T)$ is monotonically
                  restricted (under the natural pull-back along
                  parent--child seams of
                  the parent--child seam pull-back described in
                  \cite{bauerfeld-nested-tire-decompositions}) as $T$
                  descends from the root to $T^*$, with the final
                  restriction at $T^*$ being incompatible with the
                  $v_0$-side palette.
            \end{enumerate}
\end{itemize}
\end{conjecture}

\begin{thebibliography}{9}

\bibitem{tait-original}
P.~G.~Tait,
\emph{Remarks on the colouring of maps},
Proc.\ Roy.\ Soc.\ Edinburgh \textbf{10} (1880), 729.

\bibitem{bauerfeld-depth}
E.~Bauerfeld,
\emph{Plane Depth},
manuscript (math-research repository), 2026.

\bibitem{bauerfeld-nested-tire-decompositions}
E.~Bauerfeld,
\emph{Nested Tire Decompositions of Plane Triangulations},
manuscript (math-research repository), 2026.

\bibitem{bauerfeld-nested-tire-duals}
E.~Bauerfeld,
\emph{Coloring Nested Tire Dual Graphs},
manuscript (math-research repository), 2026.

\bibitem{birkhoff-reducibility}
G.~D.~Birkhoff,
\emph{The reducibility of maps},
Amer.\ J.\ Math.\ \textbf{35} (1913), 115--128.

\bibitem{birkhoff-lewis-chromatic}
G.~D.~Birkhoff and D.~C.~Lewis,
\emph{Chromatic polynomials},
Trans.\ Amer.\ Math.\ Soc.\ \textbf{60} (1946), 355--451.

\bibitem{tutte-four-colour-conjecture}
W.~T.~Tutte,
\emph{On the four-colour conjecture},
Proc.\ London Math.\ Soc.\ (2) \textbf{50} (1948), 137--149.

\bibitem{tutte-algebraic-colorings}
W.~T.~Tutte,
\emph{On the algebraic theory of graph colorings},
J.\ Combin.\ Theory \textbf{1} (1966), 15--50.

\bibitem{tutte-chromatic-sums-1973}
W.~T.~Tutte,
\emph{Chromatic sums for rooted planar triangulations: the cases $\lambda = 1$ and $\lambda = 2$},
Canad.\ J.\ Math.\ \textbf{25} (1973), 426--447.

\bibitem{heesch-untersuchungen}
H.~Heesch,
\emph{Untersuchungen zum Vierfarbenproblem},
Hochschulskriptum 810/a/b, Bibliographisches Institut, Mannheim, 1969.

\bibitem{robertson-sanders-seymour-thomas}
N.~Robertson, D.~P.~Sanders, P.~D.~Seymour, and R.~Thomas,
\emph{The four-colour theorem},
J.\ Combin.\ Theory Ser.\ B \textbf{70} (1997), 2--44.

\bibitem{dvorak-lidicky-cones}
Z.~Dvo\v{r}\'ak and B.~Lidick\'y,
\emph{Coloring count cones of planar graphs},
J.\ Graph Theory \textbf{100} (2022), 84--100.

\end{thebibliography}

\end{document}
