Independence number and disjoint theta graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl EuDML
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.
Shinya Fujita; Colton Magnant. Independence number and disjoint theta graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/637
@article{10_37236_637,
author = {Shinya Fujita and Colton Magnant},
title = {Independence number and disjoint theta graphs},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/637},
zbl = {1222.05114},
url = {http://geodesic.mathdoc.fr/articles/10.37236/637/}
}
Cité par Sources :