Edge-Colouring Geometric Complete Graphs

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $P\subset\mathbb R^2$ be a finite set of $n$ points with no three collinear. The complete geometric graph $K_P$ draws each pair as its straight closed segment. Distinct edges are crossing when their relative interiors meet, adjacent when they share an endpoint, and disjoint when the closed segments do not meet. For $X\in\{A,B,C,D\}$, let $\chi_X(P)$ be the smallest number of edge colours satisfying the following rule, and let $X(n)=\max_{|P|=n}\chi_X(P)$: A forbids equal colours on crossing pairs; B forbids equal colours on disjoint pairs; C forbids equal colours on intersecting pairs (adjacent or crossing); D forbids equal colours on pairs which do not cross (including adjacent pairs).

Statement recorded in the supplied source.

Determine $A(n),B(n),C(n),D(n)$ and their asymptotic growth. In particular, are there constants $\epsilon_A,\epsilon_B>0$ such that \[A(n)\leq(1-\epsilon_A)n,\qquad B(n)\leq(1-\epsilon_B)n\] for all sufficiently large $n$? Is $C(n)=O(n\log n)$, and, more strongly, is $C(n)=O(n)$? Is \[\lim_{n\to\infty}\frac{D(n)}n=\infty?\] [S2]

Short English statement

Determine four worst-case edge-colouring requirements for planar point sets, separating crossing, disjoint, intersecting and non-crossing pairs; resolve the accompanying linear and superlinear conjectures.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3083 (OPG-37084). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Hurtado, Ferran, Edge-Colouring Geometric Complete Graphs, Open Problem Garden, node 37084. Complete problem, discussion and bibliography (including mathematical image alt text). https://www.openproblemgarden.org/op/edge_colouring_geometric_complete_graphs.