Independence Number and Disjoint Theta GraphsThe Electronic Journal of Combinatorics
AbstractThe 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.
Citation InformationShinya Fujita and Colton Magnant. "Independence Number and Disjoint Theta Graphs" The Electronic Journal of Combinatorics Vol. 18 Iss. 1 (2011)
Available at: http://works.bepress.com/colton_magnant/27/