Número de Turán para cópias disjuntas de caminhos

Abstract

The Turán number ex(n, F) is the maximum number of edges in a graph on n vertices which does not contains F as a subgraph. It is easy to determine ex(n, kF) for small graphs. However, the problem quickly grows in difficulty as we want to avoid bigger graphs or kF, the graph formed by the disjoint union of k copies of F. In the last few years, there was progress in the problem of finding ex(n, P), where P is the graph formed by the disjoint union of k paths. ex(n, P) is well known for sufficiently large n, but little is known of the problem for small n. Let P3 be a path on 3 vertices. Gorgol offered a lower bound for ex(n, kF) when F is a connected graph and, in the same paper, conjectured that this bound is tight when F = P3. In this dissertation, we offer a constructive proof for this conjecture from Gorgol, thus determining ex(n, kP3) for all n and k. We give an algorithm that finds k disjoint copies of P3 in a sufficiently dense graph G = (V, E). We also show how to find those k copies of P3 in time O(k|E|).