Edge-Partitioning a Graph into Paths: Beyond the Barát-Thomassen Conjecture

In 2006, Barát and Thomassen conjectured that there is a function f such that, for every fixed tree T with t edges, every f ( t )-edge-connected graph with its number of edges divisible by t has a partition of its edges into copies of T . This conjecture was recently verified by the current authors...

Full description

Saved in:
Bibliographic Details
Published in:Combinatorica (Budapest. 1981) 2019-04, Vol.39 (2), p.239-263
Main Authors: Bensmail, Julien, Harutyunyan, Ararat, Le, Tien-Nam, Thomassé, Stéphan
Format: Article
Language:English
Subjects:
Combinatorics
Computer Science
Discrete Mathematics
Graph theory
Mathematics
Mathematics and Statistics
Partitions (mathematics)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In 2006, Barát and Thomassen conjectured that there is a function f such that, for every fixed tree T with t edges, every f ( t )-edge-connected graph with its number of edges divisible by t has a partition of its edges into copies of T . This conjecture was recently verified by the current authors and Merker [1]. We here further focus on the path case of the Barát-Thomassen conjecture. Before the aforementioned general proof was announced, several successive steps towards the path case of the conjecture were made, notably by Thomassen [11,12,13], until this particular case was totally solved by Botler, Mota, Oshiro andWakabayashi [2]. Our goal in this paper is to propose an alternative proof of the path case with a weaker hypothesis: Namely, we prove that there is a function f such that every 24-edge-connected graph with minimum degree f ( t ) has an edge-partition into paths of length t whenever t divides the number of edges. We also show that 24 can be dropped to 4 when the graph is eulerian.
ISSN:0209-9683
1439-6912
DOI:10.1007/s00493-017-3661-5