UVictoria Discrete Math Seminar: Mengru Lin

A geometric graph $G$ is a graph $G$ whose vertices are drawn in the plane such that no three vertices are collinear, and each edge of G is a straight line segment. A geometric homomorphism from geometric graph $G$ to geometric graph $H$ is a homomorphism that preserves crossings. Similar to the regular chromatic number, the geochromatic number of a geometric graph $G$ is the smallest integer $n$ such that there is a geometric homomorphism from $G$ to a geometric clique $K_n$.

In this talk, we will particularly discuss the relation between chromatic numbers and geochromatic numbers. Even for a bipartite graph, its geochromatic number can be unbounded. However, if the graph is not too "dense", for example, every pair of crossing has distance at least $2$, then its geochromatic number is bounded by a constant.