Home » Keyword index

geometric graph


Graph Theory » Coloring » Vertex coloring

Circular colouring the orthogonality graph ★★

Author(s): DeVos; Ghebleh; Goddyn; Mohar; Naserasr

Let $ {\mathcal O} $ denote the graph with vertex set consisting of all lines through the origin in $ {\mathbb R}^3 $ and two vertices adjacent in $ {\mathcal O} $ if they are perpendicular.

Problem   Is $ \chi_c({\mathcal O}) = 4 $?

Keywords: circular coloring; geometric graph; orthogonality

Posted by mdevos
updated September 28th, 2009
4 comments
Graph Theory » Coloring » Vertex coloring

Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The Odd Distance Graph, denoted $ {\mathcal O} $, is the graph with vertex set $ {\mathbb R}^2 $ and two points adjacent if the distance between them is an odd integer.

Question   Is $ \chi({\mathcal O}) = \infty $?

Keywords: coloring; geometric graph; odd distance

Posted by mdevos
updated March 19th, 2012
8 comments
Graph Theory » Topological G.T. » Drawings

Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set $ P \subseteq {\mathbb R}^2 $ is $ n $-universal if every $ n $ vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in $ P $, and all edges are (non-intersecting) straight line segments.

Question   Does there exist an $ n $-universal set of size $ O(n) $?

Keywords: geometric graph; planar graph; universal set

Posted by mdevos
updated May 22nd, 2007
add new comment
Syndicate content