Hamiltonicity and colorings of arrangement graphs

DOI10.1016/j.dam.2006.04.006zbMath1108.05058MaRDI QIDQ860408

Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu

Publication date: 9 January 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.006

zbMATH Keywords

connectivity; Hamilton path; planar graph; coloring; Hamilton cycle; projective-planar graph; Hamilton decomposition; circle and pseudocircle arrangement; line and pseudoline arrangement

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C45: Eulerian and Hamiltonian graphs

Uses Software

• Cinderella

Cites Work

• Hamiltonian decomposition of Cayley graphs of degree 4
• Proof of a conjecture of Burr, Grünbaum, and Sloane
• Arrangement graphs: A class of generalized star graphs
• Planar graphs: Theory and algorithms
• 4-connected projective planar graphs are Hamiltonian
• Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete
• A Theorem on Planar Graphs
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Bounding the number of embeddings of 5-connected projective-planar graphs
• PROPERTIES OF ARRANGEMENT GRAPHS
• A theorem on paths in planar graphs
• Sweeps, arrangements and signotopes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item