Independence number and disjoint theta graphs
type: Item
instance of: scholarly article
title: Independence number and disjoint theta graphs
zbMATH Open document ID: 1222.05114
author: Shinya Fujita
author: Colton Magnant
published in: The Electronic Journal of Combinatorics
publication date: 2011-07-29T00:00:00Z
full work available at URL: https://eudml.org/doc/225730
full work available at URL: v18i1p150.html
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 5933973
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5933973