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

\documentclass{amsart}

\usepackage{amssymb}
\usepackage{graphicx}

\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{Coloring Nested Tire Dual Graphs}

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

\subjclass[2010]{Primary }

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

\date{}

\dedicatory{}

\begin{abstract}
This is a follow-up to \cite{bauerfeld-nested-tires}, which
establishes the basic vocabulary of tire graphs $T$ and dual
depth.  Building on those definitions, we define the
\emph{partial tire dual} $D(T)$ and analyse its structure in the
spoke-only case (a corona graph $C_{n+m} \circ K_1$), prove the
tire-component lemma
exhibiting every BFS-level component as a tire graph, give an
edge-vertex coloring bijection that reduces counting proper
$3$-edge-colorings of $D(T)$ to counting proper $3$-vertex-colorings
of a cycle, and develop the tire-annular-subgraph, face-connector,
and inner/outer-spoke structures in $G'$.  A concluding section
records a Latin-substructure conjecture for chain-pigeonhole
compatibility of adjacent tires.
\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.

This paper is the second in a series studying that structure
through the lens of \emph{nested level duals}.  The foundational
vocabulary --- level sources, levels, the inner planar dual $G'$
and its dual depth, and tire graphs --- is developed in the
companion paper \cite{bauerfeld-nested-tires}; we refer to that
paper for those definitions and rely on them throughout.  In
particular we use, without restating, the notions of:
\begin{itemize}
  \item \emph{level source} $S$ and $G$-vertex levels $\ell_G(v)$;
  \item the inner planar dual $G'$
        (\cite[Definition~1.3]{bauerfeld-nested-tires});
  \item \emph{dual depth} $\delta_G(d_f)$
        (\cite[Definition~1.4]{bauerfeld-nested-tires});
  \item \emph{tire graph} $T = (B_{\mathrm{out}}, O, E_{\mathrm{ann}})$
        with outer/inner boundaries and annular edges
        (\cite[Definition~1.5]{bauerfeld-nested-tires});
  \item face/edge counts
        (\cite[Remark~1.6]{bauerfeld-nested-tires}).
\end{itemize}

Throughout, $G = (V, E)$ is a plane maximal planar graph (a triangulation)
with a fixed planar embedding $\Pi_G$. We write $|V| = n$, so $|E| = 3n - 6$
and $G$ has $2n - 4$ triangular faces.


\begin{definition}[Partial tire dual]
\label{def:partial-tire-dual}
Let $T = (B_{\mathrm{out}}, O, E_{\mathrm{ann}})$ be a tire graph in
the sense of \cite[Definition~1.5]{bauerfeld-nested-tires}, and let
$F_{\mathrm{ann}}$
denote the set of triangular faces of $T$ in the tire tread
(the closed region between $B_{\mathrm{out}}$ and $B_{\mathrm{in}}$).  The \emph{partial
tire dual} of $T$, written $D(T)$, is the graph defined as follows.

\emph{Vertices.}
\begin{enumerate}
  \item[(V1)] For each face $f \in F_{\mathrm{ann}}$, an
        \emph{interior vertex} $d_f$ of $D(T)$.
  \item[(V2)] For each edge $e \in E(B_{\mathrm{out}})$, a
        \emph{leaf vertex} $\ell_e^{\mathrm{out}}$.
  \item[(V3)] For each occurrence of an edge in the closed walk
        $B_{\mathrm{in}}$ (= the outer-face boundary walk of $O$),
        a \emph{leaf vertex} $\ell_e^{\mathrm{in}}$.  (When $O$ is
        $2$-connected each edge appears once; cut-vertices and
        bridges of $O$ may cause an edge or vertex to appear more
        than once.)
\end{enumerate}

\emph{Edges.}
\begin{enumerate}
  \item[(E1)] For each edge $e \in E(T)$ whose two incident faces both
        lie in $F_{\mathrm{ann}}$ (an \emph{interior annular edge}),
        one edge $\{d_{f_1}, d_{f_2}\} \in E(D(T))$ where
        $f_1, f_2 \in F_{\mathrm{ann}}$ are the two annular faces
        incident to $e$.
  \item[(E2)] For each $e \in E(B_{\mathrm{out}})$, one edge
        $\{d_f, \ell_e^{\mathrm{out}}\} \in E(D(T))$ where
        $f \in F_{\mathrm{ann}}$ is the unique annular face incident
        to $e$.  The leaf $\ell_e^{\mathrm{out}}$ has degree $1$.
  \item[(E3)] For each occurrence of $e$ on the boundary walk
        $B_{\mathrm{in}}$, one edge
        $\{d_f, \ell_e^{\mathrm{in}}\} \in E(D(T))$ where
        $f \in F_{\mathrm{ann}}$ is the annular face incident to $e$
        on the side of that occurrence.  The leaf
        $\ell_e^{\mathrm{in}}$ has degree $1$.
\end{enumerate}
\end{definition}

\begin{figure}[h]
\centering
\includegraphics[width=0.78\textwidth]{fig_partial_tire_dual.png}
\caption{The partial tire dual $D(T)$ (purple squares + orange
diamonds) drawn on top of a small tire graph $T$ (faint) with $m = 6$
and $k = 4$.  The ten interior vertices $d_f$ at the centroids of the
annular triangles form a single $10$-cycle (solid purple); each
boundary edge of the tire tread (either of $B_{\mathrm{out}}$ or
of $B_{\mathrm{in}}$) contributes a degree-$1$ leaf (orange diamond)
attached to the unique annular face incident to it (dashed orange),
giving the structure $C_{10} \circ K_1$ of
Proposition~\ref{prop:partial-tire-dual-structure}.}
\label{fig:partial-tire-dual-example}
\end{figure}

\begin{figure}[h]
\centering
\includegraphics[width=0.85\textwidth]{fig_partial_tire_dual_bridge.png}
\caption{Partial tire dual $D(T)$ when the inner outerplanar graph
$O$ has a bridge --- here a non-trivial edge cut connecting two
disjoint triangles.  $B_{\mathrm{out}}$ is a $4$-cycle on
$\{0,1,2,3\}$ and $O$ is the barbell: triangle $\{4,5,6\}$ together
with triangle $\{7,8,9\}$ joined by the bridge edge $6$--$7$ (removing
the bridge disconnects $O$).  Because both faces incident to the
bridge are annular triangles, the bridge contributes an
\emph{interior dual edge} (highlighted in red) rather than two
leaves; consequently the interior dual subgraph is no longer the
single $(n+m)$-cycle of
Proposition~\ref{prop:partial-tire-dual-structure}, but a theta
graph: the two trivalent vertices $d_5, d_6$ (the bridge-incident
annular faces) are joined by three internally vertex-disjoint paths
in $D(T)$.  Leaves come only from $B_{\mathrm{out}}$ ($n = 4$ leaves)
and the six non-bridge edges of $O$ ($m_{\partial} = 6$ leaves,
three for each triangle).}
\label{fig:partial-tire-dual-bridge}
\end{figure}

\begin{proposition}[Structure of $D(T)$ when the annular triangulation
is spoke-only]
\label{prop:partial-tire-dual-structure}
Suppose $B_{\mathrm{out}}$ is a simple cycle of length $n$, $O$ is a
$2$-connected outerplanar graph whose outer-face cycle
$B_{\mathrm{in}}$ has length $m$, and $E_{\mathrm{ann}}$ consists only
of \emph{spokes} (edges with one endpoint in $V(B_{\mathrm{out}})$ and
one in $V(B_{\mathrm{in}})$).  Then each face $f \in F_{\mathrm{ann}}$
has exactly one boundary edge (on $B_{\mathrm{out}}$ or
$B_{\mathrm{in}}$) and two interior annular edges, and consequently
$D(T)$ is isomorphic to the corona graph $C_{n+m} \circ K_1$: a cycle
of length $n + m$ on the interior vertices $\{d_f\}$, with one leaf
attached to each cycle vertex.

In particular, $|V(D(T))| = 2(n+m)$ and $|E(D(T))| = 2(n+m)$.
\end{proposition}

\begin{proof}
Each annular triangle $f$ in a spoke-only triangulation has the form
$\{x, y, z\}$ with $x \in V(B_{\mathrm{out}})$, $y \in V(B_{\mathrm{in}})$,
and $z$ also in $V(B_{\mathrm{out}}) \cup V(B_{\mathrm{in}})$.  Of its
three edges, the one between the two same-side vertices
($x$-$z$ if both on $B_{\mathrm{out}}$, or $y$-$z$ if both on
$B_{\mathrm{in}}$) is a boundary edge of the tire tread; the
other two edges are spokes.

So each $d_f$ has degree $3$ in $D(T)$: two from interior edges (= spokes
shared with adjacent annular faces) and one leaf.  The induced subgraph
on $\{d_f : f \in F_{\mathrm{ann}}\}$ is $2$-regular; together with the
connectedness of the tire tread this forces it to be a single
cycle.  By \cite[Remark~1.6]{bauerfeld-nested-tires}, the cycle has length $n + m$,
and there are also $n + m$ leaves attached one-per-cycle-vertex.
\end{proof}

\begin{proposition}[Source-side simple-cycle property]
\label{prop:no-level-d-pinch}
Let $G$ be a maximal planar graph with planar embedding $\Pi_G$ and
single-vertex source $v_0$.  Let $d \geq 1$, $v \in L_d$, and let
$C'$ be a connected component of $G'_d$ such that $v$ is incident to
some face in $F_{C'}$.  Then the depth-$d$ faces in $F_{C'}$ incident
to $v$ form a single contiguous arc in $v$'s rotation in $\Pi_G$.

Equivalently: for any such component, the source-side boundary of
$R_{C'}$ is a simple cycle in $L_d$ (no cut-vertices at level $d$).
\end{proposition}

\begin{proof}
Suppose for contradiction that the depth-$d$ faces in $F_{C'}$ at $v$
lie in two or more disjoint arcs of $v$'s rotation.  Adjacent vertices
in $G$ differ in level by at most $1$, so a face at $v$ has depth
exactly $d$ iff both other vertices have level $\geq d$, and depth
$\leq d-1$ iff at least one has level $d-1$.  Hence the gaps between
the depth-$d$ arcs at $v$ are populated by level-$(d-1)$ neighbours of
$v$, occurring in at least two disjoint arcs of $v$'s rotation.  Pick
$p$ in one such gap and $q$ in another.

The BFS ball $G[L_{<d}]$ is connected, so there exists a simple path
$P$ in $G[L_{<d}]$ from $p$ to $q$.  Define the closed walk
\[
    W \;:=\; v \to p \to P \to q \to v.
\]
Every vertex of $P$ lies in $L_{<d}$, while $\ell(v) = d$, so $v$ is
distinct from every vertex of $P$; $P$ is simple, so its internal
vertices are distinct; and $p \neq q$ since they lie in different gaps.
Hence $W$ is a simple cycle in $G$.

By the Jordan curve theorem, the planar embedding of $W$ divides $\Pi_G$
into two regions.  In $v$'s rotation, the edges $v-p$ and $v-q$ lie at
two specific positions, and they split the rotation into two arcs;
each arc lies in one of the two regions determined by $W$.  By choice
of $p, q$, the two arcs of depth-$d$ faces at $v$ in $F_{C'}$ lie in
different regions of $W$ (i.e., one arc on each side).

Since $C'$ is connected in $G'$ and contains depth-$d$ faces in both
arcs, there is a dual path $f_1, f_2, \ldots, f_k$ in $G'_d$ with
$f_1, f_k \in F_{C'}$ incident to $v$ in different arcs, and with the
intermediate faces $f_2, \ldots, f_{k-1}$ not incident to $v$ (a
shortest such dual path).  Consecutive faces $f_i, f_{i+1}$ share an
edge $e_i$ of $G$; for $i \geq 2$, both endpoints of $e_i$ lie in
$L_{\geq d}$ (since neither $f_i$ nor $f_{i+1}$ is incident to $v$,
all six vertices of these two triangles lie in $L_{\geq d}$).  In
particular, $e_i$ shares no endpoint with $W$ except possibly $v$ ---
and $v$ is excluded from $f_2, \ldots, f_{k-1}$.

A planar edge with neither endpoint on a simple closed planar curve
$W$ has both of its incident faces on the same side of $W$.  Applying
this to each $e_i$ ($i \geq 2$) inductively: starting from $f_2$ on
the same side of $W$ as $f_1$ (their shared edge $e_1 = w-w'$ opposite
to $v$ in $f_1$ has $w, w' \in L_{\geq d}$ and hence is not on $W$),
the path $f_2 \to f_3 \to \cdots \to f_{k-1} \to f_k$ stays on one
side of $W$.

But $f_1$ and $f_k$ lie on different sides of $W$ (by construction),
contradicting the conclusion that the entire path lies on one side.
\end{proof}

\begin{lemma}[Tire-component lemma]
\label{lem:tire-component}
Let $G$ be a maximal planar graph and let $S \subseteq V(G)$ be a level
source.  Fix a plane embedding $\Pi_G$ of $G$ in which $S$ lies on the
outer face (such an embedding exists for any planar graph and any
single-vertex source).  For $d \geq 0$, let
\[
    G'_d \;:=\; G'\bigl[\,\{d_f \in V(G') : \delta_G(d_f) = d\}\,\bigr]
\]
be the inner-dual subgraph on dual vertices of dual depth $d$, and let
$C'$ be a connected component of $G'_d$.  Write
$F_{C'} := \{f : d_f \in V(C')\}$,
$V_{C'} := \bigcup_{f \in F_{C'}} V(f)$, and let $C := G[V_{C'}]$ inherit
its embedding from $\Pi_G$.  Set $R_{C'} := \bigcup_{f \in F_{C'}} f
\subseteq |\Pi_G|$.

Then $C$, with the inherited embedding, is a tire graph in the sense of
\cite[Definition~1.5]{bauerfeld-nested-tires}.  Its outer boundary
$B_{\mathrm{out}}$ is the side of $R_{C'}$ closer to $S$ in $\Pi_G$,
namely the level-$d$ subgraph $G[V_{C'} \cap L_d]$ (a simple cycle or
single vertex); its inner outerplanar graph is $O = G[V_{C'} \cap
L_{d+1}]$, and its inner boundary $B_{\mathrm{in}}$ is the outer-face
boundary closed walk of $O$ in the inherited embedding (a simple cycle
when $O$ is $2$-connected, a non-simple closed walk in general).  The
triangular faces of $C$ inside the closed boundary region are exactly
the faces of $G$ in $F_{C'}$.
\end{lemma}

\begin{proof}
\emph{Outerplanarity of the two level parts.}  By construction $S$
lies on the outer face of $\Pi_G$, so the outerplanarity lemma of
\cite{bauerfeld-depth} applies directly with $(G, \Pi_G, S)$, giving
that $G[L_{d'}]$ is
outerplanar for each $d' \geq 0$.  Subgraphs of outerplanar graphs are
outerplanar, so $G[V_{C'} \cap L_d]$ and $G[V_{C'} \cap L_{d+1}]$ are
both outerplanar.

\emph{Layer containment.}  Each $f \in F_{C'}$ has at least one vertex
at level $d$, and adjacent vertices in $G$ differ in level by at most
$1$; combined with $\delta_G(d_f) = d$, this forces
$V(f) \subseteq L_d \cup L_{d+1}$.  Hence $V_{C'} \subseteq L_d \cup
L_{d+1}$, and $C$ has vertex partition
$V_{C'} = (V_{C'} \cap L_d) \sqcup (V_{C'} \cap L_{d+1})$.

\emph{Boundary edges are monochromatic in level.}  Each edge $e$ on
$\partial R_{C'}$ separates a face $f \in F_{C'}$ from a face
$f' \notin F_{C'}$.  Because $f$ and $f'$ share the edge $e$, their
dual vertices are adjacent in $G'$; if both had depth $d$ they would
lie in the same component of $G'_d$, contradicting $d_{f} \in C'$ and
$d_{f'} \notin C'$.  Hence $\delta_G(d_{f'}) \neq d$; combined with
the bounded-step property of $\delta$ across $G'$-adjacent faces,
$\delta_G(d_{f'}) \in \{d-1, d+1\}$.
\begin{itemize}
\item If $\delta_G(d_{f'}) = d - 1$, the third vertex $w$ of
      $f' = \{u, v, w\}$ (where $u, v$ are the endpoints of $e$) has
      $\ell(w) = d - 1$.  Each of $u, v$ has $\ell \in \{d, d+1\}$
      (from $V(f) \subseteq L_d \cup L_{d+1}$) and is adjacent to $w$,
      forcing $\ell(u), \ell(v) \in \{d-2, d-1, d\} \cap \{d, d+1\} =
      \{d\}$.
\item If $\delta_G(d_{f'}) = d + 1$, then all three vertices of $f'$
      lie in $L_{\geq d+1}$, so in particular $\ell(u) = \ell(v) =
      d + 1$.
\end{itemize}
Each connected boundary component thus carries a single type at every
edge: any vertex on a boundary component has two boundary edges
incident to it (by R1, see below), both of the same type, so its
level is fixed.  Therefore each boundary component of $\partial R_{C'}$
is monochromatic in level.

\emph{Boundary structure.}  Each connected component of
$\partial R_{C'}$ traces a closed walk in $G$ that, by the
monochromaticity above, lies entirely in $L_d$ or entirely in
$L_{d+1}$.  By Proposition~\ref{prop:no-level-d-pinch}, the depth-$d$
faces of $F_{C'}$ at any $v \in L_d \cap V_{C'}$ form a single
contiguous arc in $v$'s rotation, so the source-side boundary walk
visits each $L_d$-vertex of $V_{C'}$ exactly once: it is a simple
cycle.  At vertices $v \in L_{d+1} \cap V_{C'}$ the depth-$d$ faces
may split into multiple arcs of $v$'s rotation; this corresponds
exactly to $v$ being a cut-vertex of $O$, and the inner-side
boundary walk visits $v$ correspondingly many times --- which is
already accommodated by \cite[Definition~1.5]{bauerfeld-nested-tires} (where
$B_{\mathrm{in}}$ is the outer-face boundary closed walk of $O$, not
necessarily a simple cycle).

\emph{Outer boundary.}  Because $S$ lies on the outer face of $\Pi_G$,
the boundary curve(s) of $R_{C'}$ on the $L_d$ side are closer to $S$
in the embedding.  In the inherited embedding of $C$, the unique
unbounded face is the merged region containing the rest of $\Pi_G$
outside $R_{C'}$ on the $S$ side, so its boundary --- a simple cycle
on $L_d$ (or a single vertex when $V_{C'} \cap L_d = \{v_0\}$, the
$d = 0$ case) --- serves as $B_{\mathrm{out}}$.  We set
$B_{\mathrm{out}} := G[V_{C'} \cap L_d]$ if this is a cycle, and
the single vertex $\{v_0\}$ in the degenerate case.

\emph{Inner outerplanar graph.}  By the outerplanarity lemma of
\cite{bauerfeld-depth}, $G[V_{C'} \cap L_{d+1}]$ is outerplanar.  We set $O :=
G[V_{C'} \cap L_{d+1}]$.  The boundary curve(s) of $R_{C'}$ on the
$L_{d+1}$ side are exactly the boundary of $O$'s outer face in the
inherited embedding; this outer-face boundary is a single closed walk
that traces around $O$ from the outside, traversing any bridge edge
twice and visiting cut-vertices multiple times.  This walk is the
inner boundary $B_{\mathrm{in}}$.  No further restriction on $O$'s
internal structure is needed: when $R_{C'}$ has more than two
boundary components in the surface-classification sense (i.e.\
several disjoint simple cycles on $L_{d+1}$), these correspond
precisely to the multiple connected components or bridge crossings of
$O$, and the outer-face boundary closed walk of $O$ captures them
collectively.

\emph{Tire structure.}  The triangular faces of $C$ inside the closed
boundary region are by construction the depth-$d$ faces in $F_{C'}$,
and the edges of $C$ are $E(B_{\mathrm{out}}) \cup E(O) \cup
E_{\mathrm{ann}}$ where $E_{\mathrm{ann}}$ are the edges of $G$
between $V_{C'} \cap L_d$ and $V_{C'} \cap L_{d+1}$ that bound a face
of $F_{C'}$.
\end{proof}

\begin{theorem}[Tire treads partition the bounded faces]
\label{thm:tread-partition}
Let $G$ be a maximal planar graph with planar embedding $\Pi_G$ and
let $S \subseteq V(G)$ be a level source lying on the outer face.
For each $d \ge 0$ and each connected component $C'$ of $G'_d$, let
$T^{(d, C')}$ denote the tire graph supplied by
Lemma~\ref{lem:tire-component}, with tire tread
$R_{C'} \subseteq |\Pi_G|$.  Then the collection of treads
\[
   \mathcal{R}(G, S) \;:=\;
   \bigl\{\, R_{C'} \,:\, d \ge 0,\;
   C' \text{ a connected component of } G'_d \,\bigr\}
\]
partitions the bounded part of $|\Pi_G|$:
\begin{enumerate}
  \item[(i)] every bounded face $f$ of $G$ is contained in exactly
        one tread $R_{C'} \in \mathcal{R}(G, S)$;
  \item[(ii)] distinct treads in $\mathcal{R}(G, S)$ have disjoint
        interiors and may share only boundary edges or vertices.
\end{enumerate}
\end{theorem}

\begin{proof}
\emph{Existence and uniqueness.}  Each bounded face $f \in F(G)$
has a uniquely-defined dual depth $\delta_G(d_f) \in \mathbb{Z}_{\ge
0}$, so the dual vertex $d_f$ lies in $G'_d$ for $d =
\delta_G(d_f)$ and in no other $G'_{d'}$.  Within $G'_d$, the
vertex $d_f$ belongs to exactly one connected component $C'$.  By
Lemma~\ref{lem:tire-component}, $F_{C'}$ is precisely the set of
faces $f' \in F(G)$ with $d_{f'} \in V(C')$; in particular $f \in
F_{C'}$, hence $f \subseteq R_{C'}$.

For any other tread $R_{C''} \in \mathcal{R}(G, S)$, the
component $C''$ is either at a different depth $d' \ne d$ (in
which case $F_{C''}$ consists of depth-$d'$ faces and $f \notin
F_{C''}$) or at depth $d$ but a different component $C'' \ne C'$
(in which case the two components are vertex-disjoint in $G'_d$,
so again $f \notin F_{C''}$).  In both cases $f \notin R_{C''}$
(more precisely, $f$ is not one of the triangular faces of $G$ in
$F_{C''}$, so $f$'s interior is not contained in $R_{C''}$).

\emph{Disjoint interiors.}  Each tread $R_{C'}$ is the union of
its triangular faces $F_{C'} \subseteq F(G)$; distinct treads
correspond to disjoint $F_{C'}$ (by the argument above), and the
interiors of distinct $G$-faces are disjoint.  Hence interiors of
distinct treads are disjoint.

\emph{Coverage.}  Conversely, every bounded $f \in F(G)$ has $d_f
\in V(G')$ with some dual depth $d$, and thus lies in $R_{C'}$
where $C'$ is its component of $G'_d$.  So $\bigcup_{R \in
\mathcal{R}(G, S)} R$ contains every bounded face of $G$.
\end{proof}

\begin{remark}
\label{rem:tire-component-degenerate}
Either boundary part of $C$ in Lemma~\ref{lem:tire-component} may be
degenerate.  At $d = 0$ with single-vertex source $S = \{v_0\}$ the
unique component of $G'_0$ has $V_{C'} \cap L_0 = \{v_0\}$ as the
degenerate \emph{outer} boundary and $V_{C'} \cap L_1$ a cycle (the
link of $v_0$ in $G$) as the inner boundary.  Symmetrically, at
$d = D_{\max}$, $V_{C'} \cap L_{D_{\max}+1} = \emptyset$ degenerates
to a single deepest vertex serving as the \emph{inner} boundary, with
the level-$D_{\max}$ cycle as the outer boundary.
\end{remark}

\begin{remark}
\label{rem:tire-no-extra-hypotheses}
Two structural features of $R_{C'}$ that might at first appear to
obstruct the tire-graph conclusion are both already accommodated by
\cite[Definition~1.5]{bauerfeld-nested-tires}:

\emph{Cut-vertices of $O$.}  A vertex $v \in V_{C'} \cap L_{d+1}$ may
have the faces of $F_{C'}$ incident to it split into two or more
arcs in $v$'s rotation in $\Pi_G$, separated by faces of higher
depth.  This corresponds exactly to $v$ being a cut-vertex of
$O = G[V_{C'} \cap L_{d+1}]$, and the inner boundary closed walk
$B_{\mathrm{in}}$ then visits $v$ multiple times --- once for each
arc.  No additional hypothesis is needed.

\emph{Multi-hole topology of $R_{C'}$.}  Even when $R_{C'}$ encloses
several disjoint depth-$>d$ sub-regions, the inner outerplanar graph
$O$ captures the multi-hole structure as a disconnected or
non-$2$-connected outerplanar graph (with bridges or multiple
components), and its outer-face boundary closed walk serves as
$B_{\mathrm{in}}$ traversing bridges twice and visiting cut-vertices
multiple times.

In the special case $d = 0$ with single-vertex source $S = \{v_0\}$,
$R_{C'}$ is the star of $v_0$, a topological closed disk with one
boundary cycle (the link of $v_0$); the corresponding tire graph has
degenerate outer boundary $\{v_0\}$.
\end{remark}

\begin{proposition}[Edge--vertex coloring bijection for $D(T)$]
\label{prop:edge-vertex-bijection}
Let $T$ be a tire graph satisfying the spoke-only hypothesis of
Proposition~\ref{prop:partial-tire-dual-structure} (so $D(T) \cong
C_{n+m} \circ K_1$).  Let $\Gamma \cong C_{n+m}$ be the interior
dual subgraph of $D(T)$ induced on the interior dual vertices
$\{d_f : f \in F_{\mathrm{ann}}\}$.  Then the number of proper
$3$-edge-colorings of $D(T)$ equals the number of proper
$3$-vertex-colorings of $\Gamma$, both given by
\[
    2^{n+m} + 2 \cdot (-1)^{n+m}.
\]
\end{proposition}

\begin{proof}
Write $L = n + m$, $\Gamma = C_L$.  We construct mutually inverse
bijections.

\emph{Step 1: proper $3$-edge-colorings of $D(T)$ $\leftrightarrow$
proper $3$-edge-colorings of $C_L$.}  Given a proper $3$-edge-coloring
$\chi$ of $D(T)$, the three edges incident to any $d_f$ carry three
distinct colors; in particular the two cycle edges incident to $d_f$
carry distinct colors, so $\chi|_{E(C_L)}$ is a proper $3$-edge-coloring
of $C_L$.  Conversely, given a proper $3$-edge-coloring $\psi$ of
$C_L$, the two cycle edges at any $d_f$ have distinct colors, so a
unique third color is available; assign that color to $d_f$'s leaf
edge.  The resulting extension to $D(T)$ is proper at every $d_f$ and
vacuously proper at every leaf (degree~$1$), and the two maps are
inverse to each other.  Therefore
\[
    \#\bigl\{\text{proper $3$-edge-colorings of } D(T)\bigr\}
    \;=\;
    \#\bigl\{\text{proper $3$-edge-colorings of } C_L\bigr\}.
\]

\emph{Step 2: proper $3$-edge-colorings of $C_L$ $\leftrightarrow$
proper $3$-vertex-colorings of $L(C_L) \cong C_L$.}  The line graph
$L(C_L)$ of a cycle of length $L$ is again a cycle of length $L$;
proper edge-colorings of $C_L$ are by definition proper vertex-colorings
of $L(C_L)$.

\emph{Step 3: count.}  The chromatic polynomial of the cycle is
$P(C_L, k) = (k-1)^L + (-1)^L (k-1)$; at $k = 3$ this gives
$2^L + 2 \cdot (-1)^L$.
\end{proof}

\begin{remark}
\label{rem:edge-vertex-corollary}
Proposition~\ref{prop:edge-vertex-bijection} reduces counting proper
$3$-edge-colorings of $D(T)$ to counting proper $3$-vertex-colorings of
a single cycle, giving a closed form $2^{n+m} + 2(-1)^{n+m}$ that
depends only on $n+m$ (not on the specific spoke-only annular
triangulation, nor on the chord structure of $O$).  The count is
preserved under the corona-with-$K_1$ structure of
Proposition~\ref{prop:partial-tire-dual-structure} precisely because
each degree-$1$ leaf imposes no proper-edge-coloring constraint on
itself; its color is freely determined as the missing third color at
its attached interior vertex.
\end{remark}

\begin{definition}[Tire annular subgraph]
\label{def:tire-annular-subgraph}
Let $G$ be a maximal planar graph with embedding $\Pi_G$ and inner
planar dual $G'$ (as in \cite[Definition~1.3]{bauerfeld-nested-tires} above).  Let
$T = (B_{\mathrm{out}}, O, E_{\mathrm{ann}}) \subseteq G$ be a tire
graph (\cite[Definition~1.5]{bauerfeld-nested-tires}), and let
$F_{\mathrm{ann}} \subseteq F(G)$ denote its set of annular faces.
The \emph{tire annular subgraph} of $T$ in $G'$ is
\[
  T'_{\mathrm{ann}} \;:=\; G'\bigl[\,\{d_f : f \in F_{\mathrm{ann}}\}\,\bigr],
\]
the subgraph of $G'$ induced on the dual vertices corresponding to the
annular faces of $T$.  We equip $T'_{\mathrm{ann}}$ with the planar
embedding inherited from $G'$ (which, by deletion of vertices outside
the annulus, remains a planar embedding of $T'_{\mathrm{ann}}$ in the
sense of $\Pi_G$).
\end{definition}

\begin{definition}[Tire annular face connector]
\label{def:tire-annular-face-connector}
With $G, G', T$ as in
Definition~\ref{def:tire-annular-subgraph}, let $f'$ be a face of the
tire annular subgraph $T'_{\mathrm{ann}}$ in its inherited embedding,
and let $V(f') \subseteq V(T'_{\mathrm{ann}})$ denote the set of
vertices on the boundary walk of $f'$.  The \emph{tire annular face
connector at $f'$} is the subgraph
\[
  T'_{f'} \;:=\; \bigl(\,V(f') \cup N_{G'}(V(f'))\,,\;
                       \{\,e \in E(G') : e \text{ is incident to } V(f')\,\}\,\bigr)
                \;\subseteq\; G',
\]
i.e.\ the subgraph of $G'$ on the closed $G'$-neighborhood of $V(f')$
together with every $G'$-edge incident to $V(f')$.
\end{definition}

\begin{definition}[Inner and outer spokes]
\label{def:spokes}
With $T'_{f'}$ as in
Definition~\ref{def:tire-annular-face-connector}, regard $f'$ as an
open region of $|\Pi_G|$ and write $\overline{f'}$ for its closure.
The vertices of $V(T'_{f'}) \setminus V(f')$ lie in $|\Pi_G| \setminus
\overline{f'}$ or in $f'$ (never on $\partial f'$, since the boundary
walk of $f'$ is by definition the set $V(f')$).  Partition
\[
  V(T'_{f'}) \setminus V(f') \;=\;
  V_{\mathrm{out}}(T'_{f'}) \,\sqcup\, V_{\mathrm{in}}(T'_{f'})
\]
where
\begin{align*}
  V_{\mathrm{out}}(T'_{f'}) &:= \{\, v \in V(T'_{f'}) \setminus V(f')
                              \;:\; v \notin \overline{f'} \,\}, \\
  V_{\mathrm{in}}(T'_{f'})  &:= \{\, v \in V(T'_{f'}) \setminus V(f')
                              \;:\; v \in f' \,\}.
\end{align*}
The elements of $V_{\mathrm{out}}(T'_{f'})$ are the \emph{outer
spokes} of $T'_{f'}$ (vertices not in $V(f')$ that lie outside the
region bounded by $f'$); the elements of $V_{\mathrm{in}}(T'_{f'})$
are the \emph{inner spokes} of $T'_{f'}$ (vertices not in $V(f')$
that lie inside the region bounded by $f'$).
\end{definition}

\begin{remark}
\label{rem:facial-dual-spoke-only}
In the spoke-only setting of
Proposition~\ref{prop:partial-tire-dual-structure}, the tire annular
subgraph is $T'_{\mathrm{ann}} = \Gamma \cong C_{n+m}$
(Proposition~\ref{prop:edge-vertex-bijection}).  This cycle has exactly
two faces in its inherited embedding -- one on each side of the cycle
in $\Pi_G$ -- and both face boundaries traverse all $n+m$ vertices, so
$V(f') = V(\Gamma)$ for either choice of $f'$.  Each interior dual
vertex $d_f$ has $G'$-degree $3$ (since $G$ is a triangulation), of
which two edges lie in $\Gamma$ (cycle edges) and one edge points to a
single non-annular face of $G$.  Consequently $T'_{f'}$ has $n + m$
interior vertices plus the non-annular face vertices to which they
connect, and is independent of the choice of $f'$.  When $G$ consists
only of the tire $T$ together with one source-side face inside
$B_{\mathrm{out}}$ and one $O$-side face inside $B_{\mathrm{in}}$,
$T'_{f'}$ recovers the planar dual of $T$ itself.
\end{remark}

\begin{figure}[h]
\centering
\includegraphics[width=\textwidth]{notes/fig_facial_dual_choices.png}
\caption{\label{fig:facial-dual-choices}
The bridge case: $T'_{\mathrm{ann}} = \theta(1, 3, 3)$ has three faces
$A, B, C$ in its inherited embedding, with respective vertex sets
$V(A) = \{v_0, \dots, v_5\}$, $V(B) = \{v_0, v_1, v_2, v_3\}$, and
$V(C) = \{v_0, v_3, v_4, v_5\}$.  In the surrounding maximal planar
$G$, the chord endpoints $v_0, v_3$ (the two annular faces sharing
the bridge edge) have all three $G'$-edges inside $T'_{\mathrm{ann}}$,
while each non-chord vertex $v_i$ ($i \in \{1, 2, 4, 5\}$) contributes
one $G'$-edge to an external non-annular neighbor $u_i$.  Each panel
highlights $T'_{f'}$ (blue) inside $G'$: dark circles are $V(f')$,
gray circles are $G'$-neighbors of $V(f')$ within $T'_{\mathrm{ann}}$,
and red squares are external $G'$-neighbors $u_i$.  The choice of
face $f'$ controls which external neighbors $u_i$ are pulled into
$T'_{f'}$ (face $A$ pulls in all four; face $B$ pulls in $u_1, u_2$
and face $C$ pulls in $u_4, u_5$).}
\end{figure}

\section{A conjectural Latin-style substructure}
\label{sec:latin-conjecture}

Empirical enumeration (notes \texttt{tire\_fiber\_data.tex},
\texttt{tire\_fiber\_chords.tex}, \texttt{tire\_fiber\_step2.tex},
\texttt{tire\_fiber\_step2\_large.tex}) of edge $3$-coloring
distributions on the tire annular face connector $T'_{f'}$ across
$46$ adjacent-tire pairs at $|\gamma| \in \{3, 4, 5, 6, 9, 12\}$
suggests that the chain-pigeonhole step on a shared cycle always
succeeds.  The data points to a structural mechanism: every
edge-$3$-colourable tire admits at least one ``Latin-flavoured''
boundary configuration, and adjacent tires share this same
substructure on their common cycle.

Concretely, fix a tire $T$ with inner outerplanar graph $O$ on $V(B_{\mathrm{in}})$
and let $F(O)$ be the set of $O$-faces (in the tire's plane embedding,
not counting the outer face $B_{\mathrm{in}}$).  For each $O$-face
$f \in F(O)$, let $E_{\mathrm{in}}(f) \subseteq E(B_{\mathrm{in}})$
denote the set of $B_{\mathrm{in}}$ edges on $f$'s boundary.  In the
Steiner-poor surrounding triangulation (where each $O$-face is a
single face of $G$ and dualises to a single $G'$-vertex of degree
$|E_{\mathrm{in}}(f)|$ in $T'_{f'}$), proper edge $3$-colouring of
$T'_{f'}$ requires every $O$-face to have $|E_{\mathrm{in}}(f)| \leq 3$.

Let $\sigma_{B_{\mathrm{in}}}$ denote the spoke colouring restricted to
the $|V(B_{\mathrm{in}})|$ inner-direction spoke positions on the dual
annular cycle (equivalently: $\sigma$ indexed by $E(B_{\mathrm{in}})$).
Define the \emph{Latin-flavoured set} on $\gamma = B_{\mathrm{in}}$ as
\[
   \mathcal{L}(B_{\mathrm{in}}, O)
   \;:=\; \bigl\{\,\sigma : E(B_{\mathrm{in}}) \to \{1,2,3\}
     \;\big|\; \sigma\bigl|_{E_{\mathrm{in}}(f)}\text{ is a permutation
     of }\{1,2,3\}\text{ for every } f \in F(O)\,\bigr\}.
\]
That is, on every $O$-face's $B_{\mathrm{in}}$-edge boundary, all three
colours appear exactly once (forcing $|E_{\mathrm{in}}(f)| = 3$ for
each face --- the maximally constrained case).

\begin{conjecture}[Latin-substructure conjecture]
\label{conj:latin}
For any Steiner-poor edge-$3$-colourable tire $T$ with inner
outerplanar graph $O$ such that every $O$-face has exactly $3$
$B_{\mathrm{in}}$-edges, the realisable inner-spoke projection
$\pi_D(\mathcal{C}(T'_{f'}))$ contains $\mathcal{L}(B_{\mathrm{in}}, O)$
as a subset.  Moreover, $\mathcal{L}(B_{\mathrm{in}}, O)$ is invariant
under the $S_3$ action on colours and has size at least $3! = 6$.
\end{conjecture}

\begin{conjecture}[Chain-pigeonhole compatibility from Latin substructure]
\label{conj:chain-latin}
Adjacent tires $T_1, T_2$ sharing a cycle $\gamma$ admit a joint
edge $3$-colouring whenever their respective inner-outerplanar
structures $O^{(1)}, O^{(2)}$ both satisfy
Conjecture~\ref{conj:latin}.  Equivalently:
$\pi_D^{(1)}(\mathcal{C}(T_1)) \cap \pi_U^{(2)}(\mathcal{C}(T_2))
\supseteq \mathcal{L}(\gamma, O^{(1)}) \cap \mathcal{L}(\gamma,
O^{(2)})$, and this last intersection is non-empty whenever the two
face partitions of $E(\gamma)$ induced by $O^{(1)}, O^{(2)}$ share a
common ``Latin completion.''
\end{conjecture}

The structural origin of these conjectures is the empirical
observation that the smallest tested intersections on $\gamma$ are
always exactly the $3!$ permutations of a single canonical pattern
in which each $O$-face on $\gamma$'s side receives a permutation of
$\{1,2,3\}$.  For example, at $|\gamma| = 12$ with $O^{(1)}$ given by
the chord matching $\{(0,3),(4,7),(8,11)\}$ (face structure $\{0,1,2\}
\sqcup \{4,5,6\} \sqcup \{8,9,10\} \sqcup \{3,7,11\}$), the canonical
pattern $(1,2,3,2,2,1,3,3,2,3,1,1)$ assigns the permutation $(1,2,3)$
to the first face, $(2,1,3)$ to the second, $(2,3,1)$ to the third,
and $(2,3,1)$ to the fourth.  Every face receives all three colours.

A proof of Conjecture~\ref{conj:latin} would convert the
chain-pigeonhole compatibility step into a structural theorem on
$T'_{f'}$: it is not the rough abundance of valid spoke configurations
that lets adjacent tires meet, but a specific Latin-square-flavoured
substructure dictated by the face partition of each tire's inner
outerplanar graph.  See \texttt{notes/tire\_fiber\_step2\_large.tex}
for the data underlying this conjecture and
\texttt{experiments/tire\_fiber\_counterexample\_search.log} for the
ongoing automated search.

\begin{thebibliography}{9}

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

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

\end{thebibliography}

\end{document}
