A note on coloring line arrangements (Q405217)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on coloring line arrangements |
scientific article |
Statements
A note on coloring line arrangements (English)
0 references
4 September 2014
0 references
Summary: We show that the lines of every arrangement of \(n\) lines in the plane can be colored~with \(O(\sqrt{n/ \log n})\) colors such that no face of the arrangement is monochromatic. This improves a bound of \textit{P. Bose} et al. [Discrete Math. Theor. Comput. Sci. 15, No. 3, 139--154 (2013; Zbl 1281.68119)] by a \(\Theta(\sqrt{\log n})\) factor. Any further improvement on this bound would also improve the best known lower bound on the following problem of Erdős: estimate the maximum number of points in general position within a set of \(n\) points containing no four collinear points.
0 references
line arrangement
0 references
chromatic number
0 references
coloring
0 references
hypergraphs
0 references