Department of
Applied
Mathematics

Edge-partitioning into paths for graphs of low edge-connectivity

Tereza Klimo¹ová

Abstract

(joint work with J. Bensmail, A. Harutyunyan and S. Thomasse)

The Barat-Thomassen conjecture asserts that there is a function f such that for every fixed tree T with t edges, every graph which is f(t)-edge connected with its number of edges divisible by t has a partition of its edges into copies of T. This has been recently proved by Botler, Mota, Oshiro and Wakabayashi in the case when T is a path. Bensmail, Harutyunyan, Le, and Thomasse gave an alternative proof of this statement with a slightly weaker hypothesis -- they showed that the requirement on the edge connectivity can be made independent of the length of the path as long as one requires high minimum degree (depending on the length of path). We continue this line of work by providing a weaker condition on edge-connectivity.