2024/03/24 by Debra Boutin, Boutin, Debra, Alice M. Dean +1
Computer Science · Social Sciences · #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Geographic Information Systems Studies #Historical Geography and Cartography
paper · pdf · doi:10.48550/arxiv.2403.16088
openalex publication_date 2024/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A geometric graph, G, is a graph drawn in the plane, with straight line edges and vertices in general position. A geometric homomorphism between two geometric graphs G, H is a vertex map f:G→H that preserves vertex adjacency and edge crossings. The geochromatic number of G, denoted X(G), is the smallest integer n so that there is a geometric homomorphism from G to some geometric realization of Kn. 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 Kn. It is immediately clear that χ(G)≤ X(G). This paper establishes some upper bounds on X(G) in terms of χ(G). For instance, if all crossings are at distance at least 1 from each other, then X(G)≤ 3χ(G). However, there are more precise results. If all crossing are at distance at least 2, then X(G)≤ χ(G)+2. If all crossings are at distance at least 1, and there is a graph homomorphism f: G → Kn that maps no pair of edges that cross in G to the same edge in Kn, then X(G)≤ 2n. Finally, if χ(G)∈ \2,3\ and all crossings are at distance at least 1, then X(G)≤ 2χ(G).