Colouring the triangles determined by a point set

DOI10.20382/JOCG.V3I1A5MaRDI QIDQ2968087zbMATH OpenOpenAlexFDO

Authors David R. Wood, R. Fabila-Monroy

Publication date 9 March 2017

Full work available at URL https://arxiv.org/abs/1109.3218

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

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 n^3/27+O(n^2), and if P is in convex position, the answer is n^3/24+O(n^2). We prove that for arbitrary P, the chromatic number is at most n^3/19.259+O(n^2).

Recommendations

• Bounds on the chromatic number of intersection graphs of sets in the plane
• Making triangles colorful
• The number of triangles covering the center of an \(n\)-set
• Coloring copoints of a planar point set
• Monochromatic empty triangles in two-colored point sets

Cited in

(3)

• Balanced line for a 3-colored point set in the plane
• Coloring lines and Delaunay graphs with respect to boxes
• Connecting colored point sets

This page was built for publication: Colouring the triangles determined by a point set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2968087)