Engineering a Multi-Million-Node-Per-Second Heuristic Four-Coloring Algorithm for Maximal Planar Graphs

The Four Color Theorem guarantees that every planar graph admits a proper vertex coloring with at most four colors, yet engineering a four-coloring algorithm that scales to multi-million-node planar graphs at competitive throughput has received surprisingly little attention in the literature. Theoretical four-coloring algorithms for general planar graphs (Appel and Haken 1977; Robertson, Sanders, Seymour and Thomas 1996) are designed as proof tools rather than production solvers, with quartic and quadratic worst-case complexity respectively, and to the best of our knowledge no public, maintained, benchmarkable implementation of either exists. Practical fast graph colorers (First-Fit, DSATUR, parallel speculative methods) achieve high throughput on general graphs but use Δ+1 or more colors and offer no four-coloring guarantee on planar instances. We present V18b, a single-pass heuristic four-coloring algorithm for maximal planar graphs, built on five original primitives: a maximum-degree BFS start node ("raggiera maggiore"), an MXV (Maximum eXcluded Valuation) scoring rule, the Sacro Postulato of chromatic balance via randomized tie-breaking, the Bianchetto a Cascata local repair procedure, and the Tenente Informato lazy backtracking. On Delaunay maximal planar graphs from 10^4 to 10^6 vertices, V18b sustains 2 to 6.5 million nodes per second on consumer single-thread hardware while producing valid four-colorings with chromatic balance below 0.6%. Across eleven adversarial planar graph families, V18b returns zero conflicts in 55 of 55 tests. We propose OPS/N (arc accesses per vertex) as a machine-independent efficiency metric and discuss the algorithm's Pareto positioning relative to existing baselines. We do not claim a constructive proof of the Four Color Theorem; V18b is presented as an empirical engineering contribution intended to fill a gap between theoretical four-coloring algorithms and fast general-purpose graph colorers. This deposit contains both the English version (primary) and an Italian translation of the same manuscript.