Geometrization of Graphs: Towards Bounding the Chromatic Number via High-Dimensional Embedding

Abstract

We establish a geometric framework by transforming a graph $G$ into a $(d-1)$-dimensional CW complex $U^{d-1}(G)$. This construction is achieved by systematically attaching $i$-spheres ($2\le i\le d-1$) to $G$ according to specific rules, ensuring that the $j$-th homotopy group of $U^{d-1}(G)$ are trivial for $j=0,1,\dots ,d-2$. Building upon this construction, we provide a necessary and sufficient condition for $U^{d-1}(G)$ to be embeddable into ${\mathbb{R}}^d$, which yields an upper bound for the chromatic number $\chi (G)$. To be more specific, we prove that if $G$ does not contain $K_{d+3}$ and $K_{i,d+4-i}$ ($i\in \{2,3,\dots ,\lfloor \frac{d+4}{2}\rfloor \}$) as a minor, then $U^{d-1}(G)$ embeds into ${\mathbb{R}}^d$ and $\chi (G)\le 3\cdot 2^{d-1}$. Finally, as a preliminary attempt, we extend the Discharging method to ${\mathbb{R}}^d$ and investigate the coloring problem for $(d-2)$-faces in ${\mathbb{R}}^d$.

50 pages, 8 figures, submitted