Metraipolis › archive › dc_6c2edc15e1ff

Yes, $(2K_2, K_4)$-free graphs are recolorable — arXiv:2609.28893

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.28893
License (as archived)
CC0-1.0
Archived
2026-10-08T06:36:41.388Z
SHA-256 of the archived text
a036a38a45c13e4ef8d7d9c8904a1c68a37938e4e07c428e52a0e6216f2c4b03
Stable URL of this page
https://metraipolis.com/documento/dc_6c2edc15e1ff

How to cite

Yes, $(2K_2, K_4)$-free graphs are recolorable — arXiv:2609.28893 — arXiv (en), https://arxiv.org/abs/2609.28893 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6c2edc15e1ff (Metraipolis archive dc_6c2edc15e1ff, sha256 a036a38a45c13e4ef8d7d9c8904a1c68a37938e4e07c428e52a0e6216f2c4b03)
BibTeX
@misc{dc6c2edc15e1ff,
  title = {Yes, $(2K_2, K_4)$-free graphs are recolorable — arXiv:2609.28893},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.28893},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6c2edc15e1ff; sha256 a036a38a45c13e4ef8d7d9c8904a1c68a37938e4e07c428e52a0e6216f2c4b03},
  year = {2026}
}

Archived text

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

We prove that every $(2K_2,K_4)$-free graph is recolorable. Equivalently, for every such graph $G$ and every $\ell\geq \chi(G)+1$, the reconfiguration graph of proper $\ell$-colorings of $G$, in which two colorings are adjacent if they differ on exactly one vertex, is connected. This resolves the final remaining open case in the classification of recolorable $(F_1,F_2)$-free graphs when $F_1$ and $F_2$ have at most four vertices.

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