Skip to content
Preprint

Three-edge-coloring apex cubic graphs

Aug 2026 · 1 citation
Mathematics Computer Science

Abstract

A graph $G$ is \emph{apex} if $G$ has a vertex $v$ such that $G-v$ is planar. We prove that every $2$-connected apex cubic graph is three-edge-colorable. This result gives the final piece of the proof for the well-known Tutte's three-edge-coloring conjecture from 1966 \cite{tutte}. The proof, as well as the result, generalizes that of the Four Color Theorem, which requires computer checks. As in the previous proof of the Four Color Theorem, the proof is constructive. More precisely, given a $2$-connected apex cubic graph $G$ on $n$ vertices, our reducibility and discharging procedure yields a three-edge-coloring of $G$ in $O(n^2)$ time. As an additional reproducibility check for our computer checks, independent implementations reconstructed from the detailed pseudocode (given in the appendix) using generative AI systems reproduced the required computational results. These reconstructions are not part of the mathematical justification of the theorem, but provide additional evidence for the reproducibility of the computations.

View source

Similar papers

Preprint Oct 2026

Dynamic Coloring and Graph Squares of Regular Graphs

An $r$-dynamic coloring of a graph $G$ is a proper vertex coloring in which every vertex $v$ sees at least $\min\{r,d(v)\}$ distinct colors in its neighborhood. The minimum number of colors in such a coloring is the $r$-dynamic chromatic number $\chi_r^d(G)$. We study dynamic colorings of regular graphs. A straighforwa...

Juan Gutiérrez, Grover Ugarte · 0 citations
Preprint Oct 2026

Regular $K_3$-Irregular Graphs of Every Regularity at Least Nine

For a vertex $v$ of a graph $G$, the triangle-degree $\operatorname{td}_G(v)$ is the number of triangles containing $v$. A graph is triangle-distinct, or $K_3$-irregular, if its vertex triangle-degrees are pairwise distinct. Chartrand, Erd\H{o}s, and Oellermann asked whether a regular $K_3$-irregular graph exists. We p...

Zhan-He Zhang · 1 citation · ⚡1
Preprint Sep 2026

Sufficiency of Hall's Condition for Graphic List Coloring

For finite simple graphs $G,H$ on a common vertex set $V$, we say that $H$ is $G$-colorable if $H$ admits a proper list coloring with list assignment $L(v)=N_G(v)$ for all $v\in V$. This notion of coloring a graph using the neighborhood of another graph on the same vertex set, which we call \emph{graphic list coloring}...

P. Chalise · 0 citations
Preprint Sep 2026

Rainbow connecting $2$-colorings of super-Dirac graphs

Let $G$ be a graph with minimum degree $\delta(G)\ge|V(G)|/2$. Can we color the edges of $G$ with red and blue so that every pair of non-adjacent vertices is connected by a path consisting of exactly one red edge and one blue edge? We provide an affirmative answer to this question for a class of graphs that are ``close...

J'anos Bar'at, Simona Boyadzhiyska, Andrea Freschi · 0 citations
Preprint Aug 2026

The Cayley Completion of a Graph

A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given $G$ with $n$ vertices and $m$ edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order $n$ on the same vertex set? This defines two invariants, the completi...

Rigobert Fokam Souop, Laurent Bitjoka · 2 citations · ⚡2
Preprint Aug 2026

List coloring $C_3$-free planar graphs with a sparse matching of restricted lists

A graph $G$ is $k$-choosable if it has a proper coloring for every $k$-list assignment. While every $C_3$-free planar graph is $4$-choosable, some of them are not $3$-choosable, as constructed by Voigt. Hu and Zhu conjectured that if $G$ is a $C_3$-free planar graph and $X \subseteq V(G)$ induces a bipartite subgraph,...

S. Hartke, Yu-Pei Li, Joseph Pappe et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.