Paperlane

no. 15 · Monday 16 November 2026

From Diagonal Coloring to Proper Vertex Labelings Distinguishing Adjacent Facial Sums

Zhou Guofei

math.CO

Abstract

In this paper we study proper vertex labelings of 3-connected plane graphs that give distinct boundary-vertex sums to faces sharing an edge. Let $λ(G)$ be the least $k$ for which labels from $\{0,\ldots,k\}$ suffice, and let $\laml(G)$ be its arbitrary-real-list counterpart. Our two main results are an eight-element list theorem for fullerenes and the universal bound $λ(G)\le708587$ for all 3-connected plane graphs. We establish structural nine- and eight-color bounds, classify triangulations whose vertices of degree at least five form an independent set, and determine their exact diagonal chromatic numbers. We also prove closure under triangular sums for $q\ge7$ diagonal colors, with an optimal uniform threshold. For cubic 3-connected plane graphs we obtain $λ\le14$, improving to $λ\le9$ in the bipartite case.

fields
Combinatorics
pdf ↗ page arXiv:2611.18384 ↗