Abstract
A graph G is a pair (V,E), where V is a finite set and E is a set of pairs of distinct elements of V. The elements of V are called vertices, and the elements of E are called edges. Given a graph G=(V,E), a graph decomposition of G is a set of edgedisjoint subgraphs of G that cover E. If D = {H_1,..., H_k} is a decomposition of G such that H_i is a path for every i in {1,...,k}, we say that D is a path decomposition.We say that a path decomposition D of a graph G is minimum if for every path decomposition D' of G we have D' >= D. The path number of a graph G is the size of a minimum path decomposition of G. We denote it by pn(G). According to Lovász (1968), in 1966, Erdös asked about this parameter, and Gallai stated the following conjecture.Conjecture (Gallai, 1966). If G=(V,E) is a connected graph on n vertices, then pn(G)<=(n+1)/2.This parameter is not known for most of the graph classes. Lovász (1968) found an upperbound for a similar parameter, the size of a minimum decomposition into paths and cycles.Theorem (Lovász,1968). Every connected graph on n vertices G can be decomposed into at most n/2 paths and cycles.Our plan is to investigate Gallai's conjecture, the path number of special classes of graphs, and related topics. It is known that this conjecture is true for a number of classes of graphs, it has not been settled for classes of graphs such as graphs with maximum degree four, 2kregular graphs, chordal graphs or planar graphs.We are also interested is the algorithmic aspect of the problem of finding a minimum path decomposition of a graph. We were not able to find results concerning this topic, unlike the case where one seeks vertexdisjoint paths. From this point of view we are interested in approximation algoritms.The study of this problem is justified by its relevance: a classic problem, of great interest in graph theory. Since it is an open conjecture for almost half a century, it would be quite pretentious to establish its veracity or not. Nevertheless, we believe that this study will give the student the oportunity to learn many proof techniques and understand where the difficulty of the problem lies. (AU)
