Unbounded chromatic number of associahedron graphs
For an integer $n \ge 3$ let $A_n$ be the flip graph of triangulations of a convex polygon with $n$ labelled vertices: its vertices are the triangulations, and two triangulations are adjacent when one is obtained from the other by replacing a diagonal of a convex quadrilateral by its other diagonal. It is the 1-skeleton of the $(n-3)$-dimensional associahedron, and $A_n$ is a subgraph of $A_{n+1}$. Fabila-Monroy, Flores-Peñaloza, Huemer, Hurtado, Urrutia and Wood properly colored $A_n$ with $\lceil n/2 \rceil$ colors and noted that $\chi(A_n) = O(n/\log n)$. Addario-Berry, Reed, Scott and Wood proved $\chi(A_n) = O(\log n)$, as Fabila-Monroy et al. had conjectured; they also record $\chi(A_{10}) \ge 4$, communicated by Fabila-Monroy. Oum and Wood improved the upper bound to $\chi(A_n) = O(\log \log n)$.
Problem. Is $\sup_{n \ge 3} \chi(A_n) = \infty$? Equivalently, does every fixed number of colors fail to properly color $A_n$ for some sufficiently large $n$?
Source: Fabila-Monroy, Flores-Peñaloza, Huemer, Hurtado, Urrutia and Wood (2009), Conjecture 6.2 (first part); posted by Wood on the Open Problem Garden (2015).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, associahedra, flip graphs, graph colorings
References
@article{fabilamonroy2009,
author = {Fabila-Monroy, Ruy and Flores-Pe{\~n}aloza, David and Huemer, Clemens and Hurtado, Ferran and Urrutia, Jorge and Wood, David R.},
title = {On the chromatic number of some flip graphs},
journal = {Discrete Math. Theor. Comput. Sci.},
volume = {11},
number = {2},
year = {2009},
pages = {47--56},
doi = {10.46298/dmtcs.460},
}
@misc{wood2015,
author = {Wood, David R.},
title = {Chromatic number of associahedron},
howpublished = {Open Problem Garden},
year = {2015},
url = {https://www.openproblemgarden.org/op/chromatic_number_of_associahedron},
note = {Posted 2 June 2015, updated 2019},
}
@article{addarioberry2026,
author = {Addario-Berry, Louigi and Reed, Bruce and Scott, Alex and Wood, David R.},
title = {A logarithmic bound for the chromatic number of the associahedron},
journal = {J. Comput. Geom.},
volume = {17},
number = {1},
year = {2026},
pages = {61--74},
doi = {10.20382/jocg.v17i1a3},
eprint = {1811.08972},
archivePrefix = {arXiv},
}
@misc{oum2026,
author = {Oum, Sang-il and Wood, David R.},
title = {A double-logarithmic upper bound on the chromatic number of the associahedron},
year = {2026},
eprint = {2609.39015},
archivePrefix = {arXiv},
}
@misc{aim-associahedron-chromatic,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Unbounded chromatic number of associahedron graphs}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/557-associahedron-chromatic.md},
note = {Entry 557 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00328, "Unbounded chromatic number of associahedron graphs", clopen.solutions.