PreprintCC BY 4.0arXiv
The chromatic number of the associahedron: simple and logarithmic
Abstract
Addario-Berry, Reed, Scott, and Wood (JoCG 2026) proved that the n-dimensional associahedron has chromatic number at most 22500·log3 n+O(1). We present a much simpler proof that the chromatic number of the n−1-dimensional associahedron is at most 6 log2 n + 18. Since this paper's appearance as a preliminary abstract in the Japan Conference on Discrete and Computational Geometry, Graphs, and Games held from September 7-10, 2026, the bound has been improved to O(log log n) by Oum and Wood (arXiv September 30, 2026). It is hoped that the simple method here could give insights to further improvements.
Related
- A double-logarithmic upper bound on the chromatic number of the associahedron
- On the k-Distance Chromatic Number of Unicyclic Graphs
- Minimal Cayley graphs with large chromatic number
- Geometric triangle-free graphs of large chromatic number
- Diameter-two graphs whose mutual-visibility chromatic number equals their chromatic number
BibTeX
@misc{berendsohn2026chromatic,
title = {{The chromatic number of the associahedron: simple and logarithmic}},
author = {Benjamin Aram Berendsohn and Jean Cardinal and John Iacono and László Kozma},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11426},
eprint = {2610.11426},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11426},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The chromatic number of the associahedron: simple and logarithmic
AU - Benjamin Aram Berendsohn
AU - Jean Cardinal
AU - John Iacono
AU - László Kozma
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11426
UR - https://arxiv.org/abs/2610.11426
AB - Addario-Berry, Reed, Scott, and Wood (JoCG 2026) proved that the n-dimensional associahedron has chromatic number at most 22500·log_3 n+O(1). We present a much simpler proof that the chromatic number of the n−1-dimensional associahedron is at most 6 log_2 n + 18. Since this paper's appearance as a preliminary abstract in the Japan Conference on Discrete and Computational Geometry, Graphs, and Games held from September 7-10, 2026, the bound has been improved to O(log log n) by Oum and Wood (arXiv September 30, 2026). It is hoped that the simple method here could give insights to further improvements.
ER -