| On the Chromatic Numbers of some Flip Graphs (2008) | |||||||||||||||
Abstract | |||||||||||||||
| 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 convex point set, 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. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||