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.
- 3-coloring arrangements of line segments with 4 slopes is hard
- Colorings and doubled colorings of virtual doodles
- A note on arrays of dots with distinct slopes
- General position subsets and independent hyperplanes in d-space
- scientific article; zbMATH DE number 3898910 (Why is no real title available?)
- On the number of points in general position in the plane
- Nonrepetitive colorings of line arrangements
- scientific article; zbMATH DE number 6257577 (Why is no real title available?)
This page was built for publication: A note on coloring line arrangements
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405217)
