Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Coloring and guarding arrangements

Autor
Bose, P.; Cardinal, J.; Collette, S.; Hurtado, F.; Korman, M.; Langerman, S.; Taslakian, P.
Tipus d'activitat
Article en revista
Revista
Discrete mathematics and theoretical computer science
Data de publicació
2013
Volum
15
Número
3
Pàgina inicial
139
Pàgina final
154
URL
http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2115/4371 Obrir en finestra nova
Resum
Given a simple arrangement of lines in the plane, what is the minimum number c of colors required so that we can color all lines in a way that no cell of the arrangement is monochromatic? In this paper we give worst-case bounds on the number c for both the above question and for some of its variations. Line coloring problems can be redefined as geometric hypergraph coloring problems as follows: if we define Hline¿cell as the hypergraph whose vertices are lines and edges are cells of the arrange...
Paraules clau
duality, hypergraph coloring, independent set, line arrangement, vertex cover
Grup de recerca
DCG - Discrete and Combinatorial Geometry

Participants

  • Bose, Prosenjit  (autor)
  • Cardinal, Jean  (autor)
  • Collette, Sébastien  (autor)
  • Hurtado Diaz, Fernando Alfredo  (autor)
  • Korman Cozzetti, Matias  (autor)
  • Langerman, Stefan  (autor)
  • Taslakian, Perouz  (autor)