Affordable Access

Gallai's path decomposition in planar graphs

  • Blanche, Alexandre
Publication Date
Dec 13, 2021
External links


This thesis falls within the theoretical computer science field of graph theory, and deals with a question asked in 1968 by Tibor Gallai, still unanswered as of today. Gallai conjectured that the edges of any connected graph with n vertices can be partitioned into [(n+1)/2] paths. Although this conjecture has been tackled and partially solved over the years, the property has only been proven on very specific graph classes, which include graphs in which the vertices of even degree form a forest (Pyber, 1996), graphs of maximum degree 5 (Bonamy, Perrett, 2016) or graphs of treewidth at most 3 (Botler et al., 2018). The planar graphs are the graphs that can be embedded in the plane, or drawn without edges crossing. The class of planar graphs is well-known in graph theory and has been thoroughly studied. Botler, Jiménez and Sambinelli recently confirmed the conjecture on triangle-free planar graphs.Our result consists in a proof of the conjecture on the whole class of planar graphs. This class is significantly broader and more general than those of previous results, and in our opinion constitutes an important contribution to the study of Gallai's conjecture. More precisely, we work on a stronger variant of the conjecture, proposed by Bonamy and Perrett in 2016, which states that all connected graphs on n vertices could be decomposed into [n/2] paths, with the exception of a family of dense graphs. We confirm this conjecture in the case of planar graphs, by showing that every connected 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 vertex-minimum counterexample to the statement, while the third part uses the main lemma to show that such a counterexample does not exist.

Report this publication


Seen <100 times