A note on coloring line arrangements (Q405217): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:10, 5 March 2024
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