Independence number and disjoint theta graphs (Q554004): Difference between revisions

Summary: The goal of this paper is to find vertex disjoint even cycles in graphs. For this purpose, define a \(\theta \)-graph to be a pair of vertices \(u, v\) with three internally disjoint paths joining \(u\) to \(v\). Given an independence number \(\alpha \) and a fixed integer \(k\), the results contained in this paper provide sharp bounds on the order \(f (k, \alpha )\) of a graph with independence number \(\alpha (G) \leq \alpha \) which contains no \(k\) disjoint \(\theta \)-graphs. Since every \(\theta \)-graph contains an even cycle, these results provide \(k\) disjoint even cycles in graphs of order at least \(f (k, \alpha ) + 1\). We also discuss the relationship between this problem and a generalized Ramsey problem involving sets of graphs.