Independence Number and Disjoint Theta Graphs - Fujita, Shinya; Magnant, Colton (The Electronic Journal of Combinatorics, 2011)
The goal of this paper is to find vertex disjoint even cycles in graphs. For this purpose, define a $θ$-graph to be a pair of vertices $u, v$ with three internally disjoint paths joining $u$ to $v$. Given an independence number $α$ and a fixed integer $k$, the results contained in this paper provide sharp bounds on the order $f(k, α)$ of a graph with independence number $α(G) ≤ α$ which contains no $k$ disjoint $θ$-graphs. Since every $θ$-graph contains an even cycle, these results provide $k$ disjoint even cycles in graphs of order at least $f(k, α) + 1$. We also discuss the relationship between this problem and a generalized ramsey problem involving sets of graphs.