Chromatic number of associahedron

Recomm. for undergrads: yes
Posted by: David Wood
on: June 2nd, 2015

\begin{conjecture} Associahedra have unbounded chromatic number. \end{conjecture}

An \Def{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 $n$-gon, the chromatic number is at most $\ceil{n/2}$ and at most $O(n/\log n)$. The best known lower bound is $4$ for $n=10$ [private communication, Ruy Fabila-Monroy].

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}


*[FFHHUW] Ruy Fabila-Monroy, David Flores-Penaloza, Clemens Huemer, Ferran Hurtado, Jorge Urrutia, David R. Wood. \href[On the Chromatic Number of some Flip Graphs]{}, Discrete Mathematics and Theoretical Computer Science Vol 11, No 2 (2009).

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.