A proof of the Barát-Thomassen conjecture

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

doi:10.1016/j.jctb.2016.12.006

A proof of the Barát-Thomassen conjecture

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

Department of Applied Mathematics and Computer Science

Research output: Contribution to journal › Journal article › Research › peer-review

280 Downloads (Pure)

Abstract

The Barát-Thomassen conjecture asserts that for every tree T on m edges, there exists a constant k_T such that every k_T-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 language	English
Journal	Journal of Combinatorial Theory. Series B
Volume	124
Pages (from-to)	39-55
ISSN	0095-8956
DOIs	https://doi.org/10.1016/j.jctb.2016.12.006
Publication status	Published - 2017

Keywords

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

Access to Document

10.1016/j.jctb.2016.12.006

1 s2Accepted author manuscript, 777 KB

OpenUrl availability

Full text

Cite this

@article{b4e478f773194d7ab7bc097fcc8ed009,

title = "A proof of the Bar{\'a}t-Thomassen conjecture",

abstract = "The Bar{\'a}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.",

keywords = "Bar{\'a}t-Thomassen conjecture, Large edge-connectivity, Tree-decomposition",

author = "Julien Bensmail and Ararat Harutyunyan and Le, {Tien Nam} and Martin Merker and St{\'e}phan Thomass{\'e}",

year = "2017",

doi = "10.1016/j.jctb.2016.12.006",

language = "English",

volume = "124",

pages = "39--55",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press",

}

TY - JOUR

T1 - A proof of the Barát-Thomassen conjecture

AU - Bensmail, Julien

AU - Harutyunyan, Ararat

AU - Le, Tien Nam

AU - Merker, Martin

AU - Thomassé, Stéphan

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Barát-Thomassen conjecture

KW - Large edge-connectivity

KW - Tree-decomposition

U2 - 10.1016/j.jctb.2016.12.006

DO - 10.1016/j.jctb.2016.12.006

M3 - Journal article

SN - 0095-8956

VL - 124

SP - 39

EP - 55

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

A proof of the Barát-Thomassen conjecture

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this