Alexandre Blanche PhD: « Decomposition into Gallai paths in planar graphs»

This thesis is part of the computer science field of graph theory, and deals with a question posed in 1968 by Tibor Gallai, still unanswered today. Gallai conjectured that the edges of any connected graph with n vertices could be partitioned into [(n+1)/2] paths. Although this conjecture was attacked and partially solved over the years, the property has only been proved for very specific classes of graphs, such as graphs whose even degree vertices form a forest (Pyber, 1996), graphs of degree at most 5 (Bonamy, Perrett, 2016), or graphs of tree width at most 3 (Botler et al., 2018). Planar graphs are graphs that can be plunged into the plane, i.e. drawn without edge crossings. This is a well-known class in graph theory, and widely studied. Botler, Jiménez and Sambinelli have recently confirmed the conjecture in the case of planar graphs without triangles. Our result consists in a proof of the conjecture on the general class of planar graphs. This class is notably more general than the previous results, and from our point of view constitutes an important contribution to the study of the Gallai conjecture. Specifically, we work on a stronger version of the conjecture, proposed by Bonamy and Perrett in 2016, which states that related graphs with n vertices can be decomposed into [n/2] paths, except for a family of dense graphs. We confirm this conjecture in the case of planar graphs, by proving that any planar graph except K3 and K5- (K5 minus one edge) can be decomposed into [n/2] paths. The proof is divided into three parts: the first two show the main lemma of the proof, which restricts the structure of a hypothetical counterexample with a minimum of vertices, and the third part uses this lemma to show that such a counterexample does not exist.

English
Amphi LaBRI