PreprintCC BY 4.0arXiv
Box-Delaunay graphs of large chromatic number
Abstract
For every n, we construct a 2-dimensional n-element poset whose Hasse diagram has independence number nexp(−Ω(√(log n))), and consequently, chromatic number exp(Ω(√(log n))). This also yields an n-point planar set whose box-Delaunay graph satisfies the same bounds.
Related
- Minimal Cayley graphs with large chromatic number
- Geometric triangle-free graphs of large chromatic number
- The Game Chromatic Number of Complete Multipartite Graphs with Singletons and Large Parts
- Bounded chromatic number of graphs with small clique number and large minimum degree
- On the k-Distance Chromatic Number of Unicyclic Graphs
BibTeX
@misc{tomon2026boxdelaunay,
title = {{Box-Delaunay graphs of large chromatic number}},
author = {István Tomon},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01439},
eprint = {2609.01439},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01439},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Box-Delaunay graphs of large chromatic number
AU - István Tomon
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.01439
UR - https://arxiv.org/abs/2609.01439
AB - For every n, we construct a 2-dimensional n-element poset whose Hasse diagram has independence number nexp(−Ω(√(log n))), and consequently, chromatic number exp(Ω(√(log n))). This also yields an n-point planar set whose box-Delaunay graph satisfies the same bounds.
ER -