Geodesic
A note on coloring line arrangements
The electronic journal of combinatorics, Tome 21 (2014) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 Bose et al. 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.
DOI : 10.37236/2660
Classification : 05C15, 05C65, 52C30, 68Q17
Mots-clés : line arrangement, chromatic number, coloring, hypergraphs

Eyal Ackerman    ; János Pach    ; Rom Pinchasi  1   ; Radoš Radoičić    ; Géza Tóth 

1 Technion 
@article{10_37236_2660,
     author = {Eyal Ackerman and J\'anos Pach and Rom Pinchasi and Rado\v{s} Radoi\v{c}i\'c and G\'eza T\'oth},
     title = {A note on coloring line arrangements},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {2},
     doi = {10.37236/2660},
     zbl = {1300.05088},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2660/}
}
TY  - JOUR
AU  - Eyal Ackerman
AU  - János Pach
AU  - Rom Pinchasi
AU  - Radoš Radoičić
AU  - Géza Tóth
TI  - A note on coloring line arrangements
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2660/
DO  - 10.37236/2660
ID  - 10_37236_2660
ER  - 
%0 Journal Article
%A Eyal Ackerman
%A János Pach
%A Rom Pinchasi
%A Radoš Radoičić
%A Géza Tóth
%T A note on coloring line arrangements
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2660/
%R 10.37236/2660
%F 10_37236_2660
Eyal Ackerman; János Pach; Rom Pinchasi; Radoš Radoičić; Géza Tóth. A note on coloring line arrangements. The electronic journal of combinatorics, Tome 21 (2014) no. 2. doi: 10.37236/2660

Cité par Sources :