Metraipolis › archive › dc_18353ffa494b

Geometric triangle-free graphs of large chromatic number — arXiv:2610.03517

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.03517
License (as archived)
CC0-1.0
Archived
2026-10-06T08:25:29.925Z
SHA-256 of the archived text
0991820ce4271fe3d879b1d046e4ec9e6b59112d725a5c3bdd8a09b37a388e40
Stable URL of this page
https://metraipolis.com/documento/dc_18353ffa494b

How to cite

Geometric triangle-free graphs of large chromatic number — arXiv:2610.03517 — arXiv (en), https://arxiv.org/abs/2610.03517 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_18353ffa494b (Metraipolis archive dc_18353ffa494b, sha256 0991820ce4271fe3d879b1d046e4ec9e6b59112d725a5c3bdd8a09b37a388e40)
BibTeX
@misc{dc18353ffa494b,
  title = {Geometric triangle-free graphs of large chromatic number — arXiv:2610.03517},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.03517},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_18353ffa494b; sha256 0991820ce4271fe3d879b1d046e4ec9e6b59112d725a5c3bdd8a09b37a388e40},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.03517. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We present several geometric constructions of triangle-free and large girth families of graphs with rapidly growing chromatic numbers. 1. We construct a triangle-free intersection graph of $n$ boxes in $\mathbb{R}^3$ with independence number $n(\log n)^{-1+o(1)}$, and thus chromatic number $(\log n)^{1-o(1)}$. This is the first improvement over the double logarithmic lower bound of Burling from 1965, and almost matches the best known upper bound $O(\log n)$. Moreover, the bound $o(n)$ on the independence number answers a question of Walczak. 2. We prove that if there exists a unit distance graph in $\mathbb{R}^d$ of chromatic number $r$, then there also exists an induced unit distance graph in $\mathbb{R}^d$ of girth at least $g$ and the same chromatic number. Thus, the problem of determining the maximum chromatic number of unit distance graphs with any prescribed lower bound on the girth reduces entirely to the unrestricted problem, thereby strengthening a long line of results. 3. We construct an intersection graph of $n$ lines in $\mathbb{R}^3$ with girth at least $g$ and chromatic number $\Omega_g((\log n)^{1-o(1)})$. This quantitatively improves a construction of Davies. 4. We construct a set of $n$ circles in the plane such that the tangency graph of the circles has girth at least $g$ and chromatic number $\Omega_g((\log n)^{1-o(1)})$. This quantitatively improves the result of Davies, Keller, Kleist, Smorodinsky, and Walczak, and provides an alternative solution of Ringel's circle problem. 5. We construct triangle-free ordered graphs on $n$ vertices avoiding a fixed ordered path of length three as an induced subgraph, and having chromatic number $n^{\Omega(1/\log \log n)}$. This is motivated by ordered analogues of the Gyárfás-Sumner conjecture.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-05 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Metric Geometry (math.MG).
Pagina del lavoro: https://arxiv.org/abs/2610.03517 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T08:18:48.317Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).