Metraipolis › archive › dc_f8ebd0700302

Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers — arXiv:2609.08658

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.08658
License (as archived)
CC0-1.0
Archived
2026-10-16T14:49:02.273Z
SHA-256 of the archived text
3952e55e7650c045764c557c3ad1a537850e4e679ffcbdfb89fab93c401a9114
Stable URL of this page
https://metraipolis.com/documento/dc_f8ebd0700302

How to cite

Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers — arXiv:2609.08658 — arXiv (en), https://arxiv.org/abs/2609.08658 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f8ebd0700302 (Metraipolis archive dc_f8ebd0700302, sha256 3952e55e7650c045764c557c3ad1a537850e4e679ffcbdfb89fab93c401a9114)
BibTeX
@misc{dcf8ebd0700302,
  title = {Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers — arXiv:2609.08658},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.08658},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f8ebd0700302; sha256 3952e55e7650c045764c557c3ad1a537850e4e679ffcbdfb89fab93c401a9114},
  year = {2026}
}

Archived text

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

For a tournament $T$, let $\omega(T)$ be the minimum clique number among the backedge graphs of $T$, and let $\chi(T)$ be its dichromatic number. We give a template-lifting construction. It turns a $k$-template into a regular, vertex-transitive Cayley tournament that is simultaneously $(k+1)$-$\omega$-critical and $(k+1)$-$\chi$-critical. The output is also a $(k+1)$-template. Iterating the construction, we prove that for every $k\geq3$, there is a positive even integer $m_k$ with the following property. Every $N>1$ with $N\equiv1\pmod{m_k}$ is the order of a regular, vertex-transitive Cayley tournament that is simultaneously $k$-$\omega$-critical and $k$-$\chi$-critical. This proves a conjecture of Aboulker, Aubian, Charbit, and Lopes and gives a negative answer to their bounded-certificate question when the hypothesis is $\omega(T)\geq k$. We also find the clique number of a cyclic substitution when each block satisfies $\omega=\chi$. We then describe exactly when this substitution is $\omega$-critical if the blocks are $\chi$-critical and satisfy $\omega=\chi$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.08658 — 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-16T14:32:29.865Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).