Geometrization of Graphs: Towards Bounding the Chromatic Number via High-Dimensional Embedding
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915855303966720 |
|---|---|
| author | Fang, Qiming Shao, Sihong |
| author_facet | Fang, Qiming Shao, Sihong |
| contents | 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 $χ(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 $χ(G) \leq 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_10987 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Geometrization of Graphs: Towards Bounding the Chromatic Number via High-Dimensional Embedding Fang, Qiming Shao, Sihong Combinatorics Algebraic Topology 05C10 G.2.2; G.2.1 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 $χ(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 $χ(G) \leq 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$. |
| title | Geometrization of Graphs: Towards Bounding the Chromatic Number via High-Dimensional Embedding |
| topic | Combinatorics Algebraic Topology 05C10 G.2.2; G.2.1 |
| url | https://arxiv.org/abs/2411.10987 |