%% 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 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 establish the foundational definitions for studying the
Four Colour Theorem through nested level-structures on plane
triangulations.  A \emph{level source} of a triangulation $G$
induces a BFS layering of $G$, which in turn endows the inner
planar dual $G'$ with a \emph{dual depth} grading.  We isolate the
basic object of study --- the \emph{tire graph} $T$, a plane graph
whose outer and inner boundaries bound the \emph{tire tread} $R$,
a closed region triangulated by the \emph{annular edges}
$E_{\mathrm{ann}}$ --- and record its face/edge counts.
\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.  This first
paper establishes the foundational vocabulary --- level sources,
dual depth, tire graphs, and partial tire duals --- on which
subsequent papers in the series build.  In particular, the
companion paper \cite{bauerfeld-nested-tire-duals} uses these
definitions to develop nested-cycle structure theorems and
chain-pigeonhole conjectures for tire annular subgraphs of $G'$.

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}[Level source]
A \emph{level source} of $G$ is any vertex $v \in V$; we write
$S = \{v\}$ for the level-0 source.
\end{definition}

\begin{definition}[Levels]
Given a level source $S \subseteq V$, the \emph{level} of $v \in V$ is
$\ell_G(v) = \mathrm{dist}_G(v, S)$, the graph distance from $v$ to the nearest
source vertex.
\end{definition}

\begin{definition}[Dual]
\label{def:dual}
The \emph{dual} of $G$, written $G'$, is the inner (weak) planar dual of $G$ with
respect to the embedding $\Pi_G$: it has one vertex $d_f$ for each bounded face
$f$ of $G$, and an edge joining $d_f$ and $d_{f'}$ for each edge of $G$ shared by
two bounded faces $f$ and $f'$. The unbounded outer face contributes no vertex,
and edges of $G$ on the outer boundary contribute no dual edge. Since $G$ is a
triangulation, each vertex $d_f \in V(G')$ corresponds to a triangular face $f$
of $G$, and we write $V(f) \subseteq V$ for its three incident vertices.
\end{definition}

\begin{definition}[Dual depth]
\label{def:dual-depth}
Given a level source $S \subseteq V$, the \emph{dual depth} of a dual vertex
$d_f \in V(G')$ is
\[
    \delta_G(d_f) = \min_{v \in V(f)} \ell_G(v)
        = \min_{v \in V(f)} \mathrm{dist}_G(v, S),
\]
the smallest level among the three vertices of $G$ bounding the face $f$.
\end{definition}

\begin{figure}[h]
\centering
\includegraphics[width=0.7\textwidth]{fig_dual_depth.png}
\caption{Dual depth in a stacked-ring triangulation $G$ with level source
$S = \{0\}$. Each $G$ vertex is labelled by its level $\ell$. Each bounded face
carries a dual vertex (square, joined by dashed dual edges) coloured by its dual
depth $\delta(d_f) = \min_{v \in V(f)} \ell(v)$: the central fan has depth $0$,
the inner annulus depth $1$, and the outer annulus depth $2$. The outer face
(the level-$3$ triangle) is excluded from the inner dual and carries no dual
vertex.}
\label{fig:dual-depth}
\end{figure}

\begin{definition}[Tire graph]
\label{def:tire-graph}
A \emph{tire graph} consists of a plane graph $T$ together with an
\emph{outer boundary} $B_{\mathrm{out}} \subseteq T$ and an \emph{inner
outerplanar graph} $O \subseteq T$ with $V(B_{\mathrm{out}}) \cap V(O)
= \emptyset$, where
\begin{itemize}
  \item $B_{\mathrm{out}}$ is either a simple cycle of length $\geq 3$
        or a single vertex (a \emph{degenerate outer boundary});
  \item $O$ is an outerplanar graph; its \emph{inner boundary}
        $B_{\mathrm{in}}$ is the closed walk in $O$ that traces the
        boundary of $O$'s outer face in the inherited embedding,
        which is a simple cycle when $O$ is $2$-connected and a
        non-simple closed walk in general (visiting bridges twice and
        cut-vertices multiple times); if $|V(O)| = 1$, we say $T$ has
        a \emph{degenerate inner boundary}.
\end{itemize}
At most one of $B_{\mathrm{out}}, B_{\mathrm{in}}$ may be degenerate.
The vertex and edge sets of $T$ are
\[
    V(T) = V(B_{\mathrm{out}}) \cup V(O),
    \qquad
    E(T) = E(B_{\mathrm{out}}) \cup E(O) \cup E_{\mathrm{ann}},
\]
where $E_{\mathrm{ann}}$ --- the \emph{annular edges} --- has the
property that, in the plane embedding of $T$, the closed planar
region $R$ bounded externally by $B_{\mathrm{out}}$ and internally
by $B_{\mathrm{in}}$ is partitioned into triangular faces of $T$
whose union is $R$.  We call $R$ the \emph{tire tread} of $T$.

When $B_{\mathrm{out}}$ is a simple cycle and $O$ is $2$-connected,
the tread is a closed annulus.  More generally, $R$ is a closed
planar region that may fail to be a $2$-manifold at cut-vertices of
$O$ (where two ``lobes'' of the depth-$d$ region meet at a single
vertex); the inner boundary $B_{\mathrm{in}}$ is then a non-simple
closed walk that visits the cut-vertex multiple times.  The relaxed
definition accommodates outerplanar inner graphs with bridges,
cut-vertices, or multiple connected components.  When either
boundary is degenerate, the tread is a closed disk with that vertex
as apex.
\end{definition}

\begin{figure}[h]
\centering
\includegraphics[width=0.78\textwidth]{fig_tire_example.png}
\caption{A tire graph with non-degenerate boundaries: outer boundary
$B_{\mathrm{out}}$ a $6$-cycle on vertices $0,\dots,5$ (blue), inner
boundary $B_{\mathrm{in}}$ a $4$-cycle on vertices $6,\dots,9$ (red),
inner outerplanar graph $O = B_{\mathrm{in}} \cup \{7\text{--}9\}$
(with one chord, orange), and $E_{\mathrm{ann}}$ (grey) tiling the
annulus between $B_{\mathrm{out}}$ and $B_{\mathrm{in}}$ by ten
triangular faces.}
\label{fig:tire-example}
\end{figure}

\begin{remark}
\label{rem:tire-counts}
Let $m = |V(B_{\mathrm{out}})|$ and $k = |V(B_{\mathrm{in}})|$.  By
Euler's formula on the tire tread $R$, the tire graph has $m + k$
triangular faces inside $R$ and $|E_{\mathrm{ann}}| = m + k$
annular edges when neither boundary is degenerate; when exactly one
boundary is degenerate (so $\min(m, k) = 1$), there are $m + k - 1$
triangular faces and $|E_{\mathrm{ann}}| = m + k - 1$.
\end{remark}


\begin{thebibliography}{9}

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

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

\end{thebibliography}

\end{document}
