Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.16088 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909148216557568 |
|---|---|
| author | Boutin, Debra Dean, Alice |
| author_facet | Boutin, Debra Dean, Alice |
| contents | A geometric graph, $\overline{G}$, is a graph drawn in the plane, with straight line edges and vertices in general position. A geometric homomorphism between two geometric graphs $\overline{G}$, $\overline{H}$ is a vertex map $f:\overline{G}\to\overline{H}$ that preserves vertex adjacency and edge crossings. The geochromatic number of $\overline{G}$, denoted $X(\overline{G})$, is the smallest integer $n$ so that there is a geometric homomorphism from $\overline{G}$ to some geometric realization of $K_n$. Recall that the chromatic number of an abstract graph $G$, denoted $χ(G)$, is the smallest integer $n$ for which there is a graph homomorphism from $G$ to $K_n$. It is immediately clear that $χ(G)\leq X(\overline{G})$. This paper establishes some upper bounds on $X(\overline{G})$ in terms of $χ(G)$. For instance, if all crossings are at distance at least 1 from each other, then $X(\overline{G})\leq 3χ(G)$. However, there are more precise results. If all crossing are at distance at least 2, then $X(\overline{G})\leq χ(G)+2$. If all crossings are at distance at least 1, and there is a graph homomorphism $f: G \to K_n$ that maps no pair of edges that cross in $\overline{G}$ to the same edge in $K_n$, then $X(\overline{G})\leq 2n$. Finally, if $χ(G)\in \{2,3\}$ and all crossings are at distance at least 1, then $X(\overline{G})\leq 2χ(G)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_16088 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Geochromatic Number when Crossings are Independent Boutin, Debra Dean, Alice Combinatorics A geometric graph, $\overline{G}$, is a graph drawn in the plane, with straight line edges and vertices in general position. A geometric homomorphism between two geometric graphs $\overline{G}$, $\overline{H}$ is a vertex map $f:\overline{G}\to\overline{H}$ that preserves vertex adjacency and edge crossings. The geochromatic number of $\overline{G}$, denoted $X(\overline{G})$, is the smallest integer $n$ so that there is a geometric homomorphism from $\overline{G}$ to some geometric realization of $K_n$. Recall that the chromatic number of an abstract graph $G$, denoted $χ(G)$, is the smallest integer $n$ for which there is a graph homomorphism from $G$ to $K_n$. It is immediately clear that $χ(G)\leq X(\overline{G})$. This paper establishes some upper bounds on $X(\overline{G})$ in terms of $χ(G)$. For instance, if all crossings are at distance at least 1 from each other, then $X(\overline{G})\leq 3χ(G)$. However, there are more precise results. If all crossing are at distance at least 2, then $X(\overline{G})\leq χ(G)+2$. If all crossings are at distance at least 1, and there is a graph homomorphism $f: G \to K_n$ that maps no pair of edges that cross in $\overline{G}$ to the same edge in $K_n$, then $X(\overline{G})\leq 2n$. Finally, if $χ(G)\in \{2,3\}$ and all crossings are at distance at least 1, then $X(\overline{G})\leq 2χ(G)$. |
| title | Geochromatic Number when Crossings are Independent |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2403.16088 |