Colouring the triangles determined by a point set

DOI10.20382/JOCG.V3I1A5zbMATH Open1404.05131arXiv1109.3218OpenAlexW2150278422MaRDI QIDQ2968087FDOQ2968087

Authors: David R. Wood, R. Fabila-Monroy 

Publication date: 9 March 2017

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).

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

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

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)

Cited In (2)

• Balanced line for a 3-colored point set in the plane
• 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)