A proof of the Barát-Thomassen conjecture

Julien Bensmail, Ararat Harutyunyan, Tien Nam Le, Martin Merker, Stéphan Thomassé

Research output: Contribution to journalJournal articleResearchpeer-review

166 Downloads (Pure)

Abstract

The Barát-Thomassen conjecture asserts that for every tree T on m edges, there exists a constant kT such that every kT-edge-connected graph with size divisible by m can be edge-decomposed into copies of T. So far this conjecture has only been verified when T is a path or when T has diameter at most 4. Here we prove the full statement of the conjecture.
Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Volume124
Pages (from-to)39-55
ISSN0095-8956
DOIs
Publication statusPublished - 2017

Keywords

  • Barát-Thomassen conjecture
  • Large edge-connectivity
  • Tree-decomposition

Fingerprint Dive into the research topics of 'A proof of the Barát-Thomassen conjecture'. Together they form a unique fingerprint.

Cite this