Skip to content
DraconiticResearch
Search Sources API
181,716 studies31 sourcesUpdated 13 min ago
PreprintarXiv licencearXiv

A note on decompositions into 3-chromatic graphs

  • Bertille Granet
  • Daniel Horsley
  • Jeffrey N. Santrio
Open at sourcePDFDOICite

Abstract

Delcourt and Postle recently introduced the `discharging in the dual' proof technique, leading to a breakthrough proof of Nash-Williams' conjecture on triangle decompositions. Independently, and almost simultaneously, the first and second authors built on the `condensation' method of Bryant, Dukes, Horsley, Maenhaut and Montgomery to determine the decomposition threshold of all odd cycles of length at least $73$. In this note, we explain how the `discharging in the dual' and `condensation' methods can be combined to determine the decomposition threshold of cycles of any odd length, as well as the approximate decomposition threshold of a range of other $3$-chromatic graphs.

Related

  1. A note on the list chromatic number of two matroids
    Bence Garami
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On the k-Distance Chromatic Number of Unicyclic Graphs
    Rosário Fernandes, Rúben Palma
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeneral mathematicsDOAJ
  3. Minimal Cayley graphs with large chromatic number
    James Davies, Meike Hatzel, Liana Yepremyan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Geometric triangle-free graphs of large chromatic number
    István Tomon
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  5. Box-Delaunay graphs of large chromatic number
    István Tomon
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{granet2026note,
  title = {{A note on decompositions into 3-chromatic graphs}},
  author = {Bertille Granet and Daniel Horsley and Jeffrey N. Santrio},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41266},
  eprint = {2610.41266},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41266},
}
RIS
TY  - UNPB
TI  - A note on decompositions into 3-chromatic graphs
AU  - Bertille Granet
AU  - Daniel Horsley
AU  - Jeffrey N. Santrio
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.41266
UR  - https://arxiv.org/abs/2610.41266
AB  - Delcourt and Postle recently introduced the `discharging in the dual' proof technique, leading to a breakthrough proof of Nash-Williams' conjecture on triangle decompositions. Independently, and almost simultaneously, the first and second authors built on the `condensation' method of Bryant, Dukes, Horsley, Maenhaut and Montgomery to determine the decomposition threshold of all odd cycles of length at least $73$. In this note, we explain how the `discharging in the dual' and `condensation' methods can be combined to determine the decomposition threshold of cycles of any odd length, as well as the approximate decomposition threshold of a range of other $3$-chromatic graphs.
ER  -