ICS Theory Group

ICS 269, Spring 2001: Theory Seminar

1 June 2001:
"Hamiltonicity and colorings of arrangement graphs" by Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
Javid Huseynov

ABSTRACT: Authors study connectivity, Hamiltonian path and Hamiltonian cycle decomposition, 4-edge and 3-vertex coloring for graphs arising from pseudoline (affine and projective) and pseudocircle (spherical) arrangements. Graph theoretical properties of arrangements are studied. Most interesting result is that spherical arrangements admit decompositions into two Hamiltonian cycles and 4-edge colorings. A number of conjectures and open questions accompany the results. (Appeared in SODA 2000.)