geometric graph

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.

\begin{problem} Is $\chi_c({\mathcal O}) = 4$? \end{problem}

Keywords: circular coloring; geometric graph; orthogonality

Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The \emph{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.

\begin{question} Is $\chi({\mathcal O}) = \infty$? \end{question}

Keywords: coloring; geometric graph; odd distance

Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set $P \subseteq {\mathbb R}^2$ is $n$-\emph{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.

\begin{question} Does there exist an $n$-universal set of size $O(n)$? \end{question}

Keywords: geometric graph; planar graph; universal set

Syndicate content