Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 7 min ago
PreprintCC BY 4.0arXiv

Yes, (2K2, K4)-free graphs are recolorable

  • Henry Echeverría
  • Owen Henderschedt
Open at sourcePDFDOICite

Abstract

We prove that every (2K2,K4)-free graph is recolorable. Equivalently, for every such graph G and every ℓ≥ χ(G)+1, the reconfiguration graph of proper ℓ-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 (F1,F2)-free graphs when F1 and F2 have at most four vertices.

Related

  1. Geometric triangle-free graphs of large chromatic number
    István Tomon
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  2. When are random regular triangle-free graphs bipartite?
    Gregory DeCamillis, Pu Gao
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
    Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. The Borodin--Kostochka Conjecture for Two Classes of Diamond-Free Graphs
    Alireza Fiujlaali
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Seeking the dense half in K4-free graphs
    Ignacy Buczek, Andrzej Grzesik, Piotr Kuc
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{echeverria2026k4free,
  title = {{Yes, $(2K_2, K_4)$-free graphs are recolorable}},
  author = {Henry Echeverría and Owen Henderschedt},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.28893},
  eprint = {2609.28893},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.28893},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Yes, (2K_2, K_4)-free graphs are recolorable
AU  - Henry Echeverría
AU  - Owen Henderschedt
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2609.28893
UR  - https://arxiv.org/abs/2609.28893
AB  - We prove that every (2K_2,K_4)-free graph is recolorable. Equivalently, for every such graph G and every ℓ≥ χ(G)+1, the reconfiguration graph of proper ℓ-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.
ER  -