eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2009-01-01
Vol. 11 no. 2
Graph and Algorithms
10.46298/dmtcs.460
460
journal article
On the chromatic number of some flip graphs
Ruy Fabila-Monroy
David Flores-PeĆ±aloza
Clemens Huemer
Ferran Hurtado
Jorge Urrutia
David R. Wood
https://orcid.org/0000-0001-8866-3041
Graphs and Algorithms
This paper studies the chromatic number of the following four flip graphs (under suitable definitions of a flip): the flip graph of perfect matchings of a complete graph of even order, the flip graph of triangulations of a convex polygon (the associahedron), the flip graph of non-crossing Hamiltonian paths of a set of points in convex position, and the flip graph of triangles in a convex point set. We give tight bounds for the latter two cases and upper bounds for the first two.
https://dmtcs.episciences.org/460/pdf
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]