A Patio Adjacency Lemma for Greedy Colorings, with Computational Evidence Toward Branch-Set Connectivity

We study the invariant p(G), the minimum number of palette expansions over all vertex orderings of a greedy coloring, and prove that χ(G) = 1 + p(G). Our main contribution is the Patio Adjacency Lemma (Theorem 3.4): in any optimal greedy palette-expansion coloring with expansion centers c₁,…,cₖ, the center cⱼ has, for every i < j, a neighbor in color class Aᵢ; hence every pair of color classes is joined by an edge with one endpoint at an expansion center. The lemma is proved and verified computationally on 130,000+ graphs. We then study a branch-set construction seeded by the color classes. The Patio Adjacency Lemma makes the initial configuration pairwise-adjacent at no cost; the construction maintains adjacency while attempting to repair connectivity. We prove what it guarantees unconditionally (disjointness, an adjacency invariant, and a bounded connectivity potential), and we are explicit that producing internally connected branch sets — equivalently, partitioning V(G) into k connected, pairwise-adjacent sets — is exactly Hadwiger's conjecture for that k (Open Problem 6.1), which we do not settle. On the tested graphs the construction achieved the pairwise-adjacency half universally; internal connectivity was generally not achieved. We make no claim about Hadwiger's conjecture for k ≥ 7. Changes in v24: corrected the Section 4 construction to be internally consistent; proved the connectivity-potential lemma in full; corrected an open problem that was in fact immediate; and revised Section 5 to report honestly that the experiments confirm the adjacency half, not full Kₖ-minor certificates. Code: https://github.com/mizaelantoniotovarreyes/chromatic-hadwiger Project site: https://hadwiger.oryum.ai/