Independence number and disjoint theta graphs (Q554004): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 01:37, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independence number and disjoint theta graphs |
scientific article |
Statements
Independence number and disjoint theta graphs (English)
0 references
29 July 2011
0 references
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.
0 references