Colouring the triangles determined by a point set

Ruy Fabila-Monroy, David R. Wood

Abstract


Let P be a set of n points in general position in the plane. We study the chromatic number of the intersection graph of the open triangles determined by P. It is known that this chromatic number is at least n3/27+O(n2) and, if P is in convex position, the answer is n3/24+O(n2). We prove that for arbitrary P, the chromatic number is at most n3/19.259+O(n2).

Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v3i1a5

ISSN: 1920-180X