Title: Decomposition and Separation Problems in Graphs
Data: 15 de outubro de 2024 – 3a feira – 10h - Auditório Jacy Monteiro
Student: Antônio Kaique Barroso Fernandes

Abstract: This master’s thesis primarily aims to present the problem of graph covering by rainbow paths. This problem arises in the context of separating sets, establishing a connection between graph separation issues and the challenge of decomposing a graph into paths, as proposed by the famous Gallai Conjecture. This work introduces the separating set problem, focusing on the problem proposed by Katona to find the size of the minimum separating system of the edges of a graph using paths. The text covers the history of the problem, as well as the proof presented by Bonamy, Botler, Dross, Naia, and Skokan, which showed that every graph admits a separating path system of linear size in terms of the number of vertices. Moreover, we discuss Gallai’s Conjecture and related results to provide a comprehensive view of the state of the art in graph decomposition by paths. Finally, we present original results developed during the master’s research period. Translating the problem of covering graphs with rainbow paths to the context of random graphs, we initially prove that, with high probability, for p » (log n)^{1/2} /n, every proper edge-coloring of the binomial random graph G = G(n, p) admits a covering of E(G) by O(n) rainbow paths. Then, we strengthen this result by showing that for any ε > 0 and p ≥ n^{ε−1}, the same conclusion holds.