Edge-Colouring Geometric Complete Graphs

Importance: Medium ✭✭
Author(s): Hurtado, Ferran
Subject: Geometry
Recomm. for undergrads: yes
Posted by: David Wood
on: October 19th, 2009

\begin{question} What is the minimum number of colours such that every complete geometric graph on $n$ vertices has an edge colouring such that: \begin{itemize} \item[Variant A] crossing edges get distinct colours, \item[Variant B] disjoint edges get distinct colours, \item[Variant C] non-disjoint edges get distinct colours, \item[Variant D] non-crossing edges get distinct colours. \end{itemize} \end{question}

Let $P$ be a set of $n$ points in the plane with no three collinear. Draw a straight line-segment between each pair of points in $P$. We obtain the \emph{complete geometric graph} with vertex set $P$, denoted by $K_P$.

Two edges in $K_P$ are either: \begin{itemize} \item \emph{adjacent} if they have a vertex in common, \item \emph{crossing} if they intersect at a point in the interior of both edges. \item \emph{disjoint} if they do not intersect. \end{itemize}

Let $A(n)$, $B(n)$, $C(n)$ and $D(n)$ be the minimum number of colours for the four variants.

\textbf{Variant A:} Here each colour class is a plane subgraph. Since there are point sets for which $\frac{n}{2}$ edges are pairwise crossing, $A(n)\geq\frac{n}{2}$. For an upper bound, say $P=\{v_1,\dots,v_n\}$. Colour each edge $v_iv_j$ with $i

\textbf{Conjecture.} $A(n)\leq (1-\epsilon)n$ for some $\epsilon>0$.

\textbf{Variant B:} Here edges receiving the same colour must intersect. So each colour class is a geometric thrackle. Since there are point sets for which $\frac{n}{2}$ edges are pairwise disjoint, $B(n)\geq \frac{n}{2}$. The $(n-1)$-colouring given in Variant A also works here. So $B(n)\leq n-1$.

\textbf{Conjecture.} $B(n)\leq (1-\epsilon)n$ for some $\epsilon>0$.

\textbf{Variant C:} Here each colour class is a plane matching. So each colour class has at most $\frac{n}{2}$ edges, and thus at least $n-1$ colours are always needed. Thus $C(n)\geq n-1$. Araujo [ADHNU] proved an upper bound of $C(n)\in O(n^{3/2})$.

\textbf{Conjecture.} $C(n)\in O(n\log n)$.

\textbf{Strong Conjecture.} $C(n)\in O(n)$.

\textbf{Variant D:} (This variant was recently mentioned in [Mat].) Here edges receiving the same colour must cross. Each colour class is called a \emph{crossing family} [ADHNU]. Every edge in any triangulation of $P$ requires its own colour. So if the convex hull of $P$ has only three points, then at least $3n-6$ colours are needed. Thus $D(n)\geq 3n-6$.

\textbf{Conjecture.} A super-linear number of colours are always needed; i.e., $\frac{D(n)}{n}\rightarrow\infty$ as $n\rightarrow\infty$.

A better lower bound is obtained by taking $P$ in convex position. Then $\Theta(n\log n)$ is the minimum number of colours [KK]. I am not aware of any non-trivial upper bound for arbitrary point sets $P$.


[ADHNU] G. Araujo, A. Dumitrescu, F. Hurtado, M. Noy, J. Urrutia, On the chromatic number of some geometric type Kneser graphs, \emph{Computational Geometry: Theory & Applications} 32(1):59–69, 2005 \MRhref{MR2155418}

[BHRW] Prosenjit Bose, Ferran Hurtado, Eduardo Rivera-Campo, David R. Wood. Partitions of complete geometric graphs into plane trees, \emph{Computational Geometry: Theory & Applications} 34(2):116-125, 2006. \MRhref{MR2222887}

[AEGKKPS] B. Aronov, P. Erdos, W. Goddard, D.J. Kleitman, M. Klugerman, J. Pach, L.J. Schulman, Crossing families, \emph{Combinatorica} 14(2):127–134, 1994. \MRhref{MR1289067}

[KK] Alexandr Kostochka and Jan Kratochvil. Covering and coloring polygon-circle graphs, \emph{Discrete Math.} 163(1--3):299--305, 1997. \MRhref{MR1428585}

[Mat] Jiří Matoušek. Blocking visibility for points in general position. \emph{Discrete Comput. Geom.} 42(2):219--223, 2009. \MRhref{MR2519877}

* indicates original appearance(s) of problem.