Contributors: Combinatorics, Optimization and Algorithms for Telecommunications (COATI); Inria Sophia Antipolis - Méditerranée (CRISAM); Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED); Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA); Université Paris Dauphine-PSL; Université Paris Sciences et Lettres (PSL); École normale supérieure de Lyon (ENS de Lyon); Modèles de calcul, Complexité, Combinatoire (MC2); Laboratoire de l'Informatique du Parallélisme (LIP); École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL); Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL); Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS); Institut universitaire de France (IUF); Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.); The first author was supported by ERC Advanced Grant GRACOL, project no. 320812. The second author was supported by an FQRNT postdoctoral research grant and CIMI research fellowship. The fourth author was partially supported by the ANR Project STINT under Contract ANR-13-BS02-0007; ANR-13-BS02-0007,Stint,Structures Interdites(2013); European Project: 320812,EC:FP7:ERC,ERC-2012-ADG_20120216,GRACOL(2013)
نبذة مختصرة : International audience ; 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. 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, until this particular case was totally solved by Botler, Mota, Oshiro and Wakabayashi. 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.
Processing Request
No Comments.