login/create account
Conjecture Associahedra have unbounded chromatic number.
An associahedron is the convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a fixed word and the edges correspond to single application of the associativity rule. Equivalently, the vertices of an associahedron correspond to the triangulations of a convex polygon and the edges correspond to edge flips in which a single diagonal is removed from a triangulation and replaced by a different diagonal.
The chromatic number of (the 1-skeleton of) associahedra was first considered by Fabila-Monroy et al [FFHHUW]. They proved that for the associahedron corresponding to edge flips in triangulations of a convex 
-gon, the chromatic number is at most 
and at most 
. The best known lower bound is 
for 
[private communication, Ruy Fabila-Monroy].
Update (2019): Addario Berry et al. [ARSW] proved an upper bound of 
.
Bibliography
*[FFHHUW] Ruy Fabila-Monroy, David Flores-Penaloza, Clemens Huemer, Ferran Hurtado, Jorge Urrutia, David R. Wood. On the Chromatic Number of some Flip Graphs, Discrete Mathematics and Theoretical Computer Science Vol 11, No 2 (2009).
[ARSW] Louigi Addario Berry, Bruce Reed, Alex Scott, David R. Wood. A logarithmic bound for the chromatic number of the associahedron, 2018.
* indicates original appearance(s) of problem.
Drupal
CSI of Charles University