Skip to main content
Independence Number and Disjoint Theta Graphs
The Electronic Journal of Combinatorics
  • Shinya Fujita, Maebashi Institute of Technology
  • Colton Magnant, Georgia Southern University
Document Type
Publication Date

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.


Copyright of the article remains with the author. Article obtained from the Electronic Journal of Combinatorics.

Citation Information
Shinya Fujita and Colton Magnant. "Independence Number and Disjoint Theta Graphs" The Electronic Journal of Combinatorics Vol. 18 Iss. 1 (2011) p. 1 - 27 ISSN: 1077-8926
Available at: