Geochromatic Number when Crossings are Independent

A geometric graph, Ḡ, is a graph drawn in the plane, with straight line edges and vertices in general position. A geometric homomorphism between two geometric graphs Ḡ, H̄ is a vertex map f:Ḡ̄ that preserves vertex adjacency and edge crossings. The geochromatic number of Ḡ, denoted X(Ḡ), is the smallest integer n so that there is a geometric homomorphism from Ḡ to some geometric realization of Kₙ. 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ₙ. It is immediately clear that χ(G)≤ X(Ḡ). This paper establishes some upper bounds on X(Ḡ) in terms of χ(G). For instance, if all crossings are at distance at least 1 from each other, then X(Ḡ)≤ 3χ(G). However, there are more precise results. If all crossing are at distance at least 2, then X(Ḡ)≤ χ(G)+2. If all crossings are at distance at least 1, and there is a graph homomorphism f: G → Kₙ that maps no pair of edges that cross in Ḡ to the same edge in Kₙ, then X(Ḡ)≤ 2n. Finally, if χ(G)∈ \2,3\ and all crossings are at distance at least 1, then X(Ḡ)≤ 2χ(G).