Edge-disjoint odd cycles in graphs with small chromatic number
Annales de l'institut Fourier (1999)
- Volume: 49, Issue: 3, page 783-786
- ISSN: 0373-0956
Access Full Article
top
Abstract
topHow to cite
topBerge, Claude, and Reed, Bruce. "Edge-disjoint odd cycles in graphs with small chromatic number." Annales de l'institut Fourier 49.3 (1999): 783-786. <http://eudml.org/doc/75362>.
@article{Berge1999,
abstract = {For a simple graph, we consider the minimum number of edges which block all the odd cycles and the maximum number of odd cycles which are pairwise edge-disjoint. When these two coefficients are equal, interesting consequences appear. Similar problems (but interchanging “vertex-disjoint odd cycles” and “edge-disjoint odd cycles”) have been considered in a paper by Berge and Fouquet.},
author = {Berge, Claude, Reed, Bruce},
journal = {Annales de l'institut Fourier},
keywords = {graph; games; positional game; monochromatic odd cycle; winning strategy; chromatic number; edge-disjoint odd cycles},
language = {eng},
number = {3},
pages = {783-786},
publisher = {Association des Annales de l'Institut Fourier},
title = {Edge-disjoint odd cycles in graphs with small chromatic number},
url = {http://eudml.org/doc/75362},
volume = {49},
year = {1999},
}
TY - JOUR
AU - Berge, Claude
AU - Reed, Bruce
TI - Edge-disjoint odd cycles in graphs with small chromatic number
JO - Annales de l'institut Fourier
PY - 1999
PB - Association des Annales de l'Institut Fourier
VL - 49
IS - 3
SP - 783
EP - 786
AB - For a simple graph, we consider the minimum number of edges which block all the odd cycles and the maximum number of odd cycles which are pairwise edge-disjoint. When these two coefficients are equal, interesting consequences appear. Similar problems (but interchanging “vertex-disjoint odd cycles” and “edge-disjoint odd cycles”) have been considered in a paper by Berge and Fouquet.
LA - eng
KW - graph; games; positional game; monochromatic odd cycle; winning strategy; chromatic number; edge-disjoint odd cycles
UR - http://eudml.org/doc/75362
ER -
References
top- [1] C. BERGE, Hypergraphs, Combinatorics of finite sets, North-Holland, Amsterdam, New York, 1989.
- [2] C. BERGE, J.-L. FOUQUET, On the optimal transversals of the odd cycles, Discrete Math., 169 (1997), 169-176. Zbl0883.05088MR98c:05094
- [3] C. BERGE, B. REED, Optimal packings of edge disjoint odd cycles, to appear. Zbl0945.05048
- [4] P.C. CATLIN, Hajós'Graph Coloring Conjecture, J. of Combinat. Theory, B26 (1979), 268-274. Zbl0385.05033MR81g:05057
- [5] J.-C. FOURNIER, M. LAS VERGNAS, Une classe d'hypergraphes bichromatiques, Discrete Math., 2 (1979), 407-410 (see also [1], p. 156). Zbl0247.05127MR46 #5156
- [6] L. LOVÁSZ, Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2 (1972), 253-267. Zbl0239.05111MR46 #1624
- [7] L. LOVÁSZ, Private communication.
- [8] B. REED, Mango and Blueberries (to appear).
- [9] B. REED, Tree widht and tangles, a new measure of connectivity and some applications, Survey in Combinatorics, R. Bailey editor, London Math. Soc. Lecture Notes Series 241, Cambridge University Press, Cambridge 1997, 87-162. Zbl0895.05034
- [10] C. THOMASSEN, On the presence of disjoint subgraphs of a specified type, J. of Graph Theory, 12 (1988), 101-111. Zbl0662.05032MR89e:05174
- [11] B. TOFT, T.R. JENSEN, Graph coloring problems, Wiley Interscience, 1995. Zbl0855.05054MR95h:05067
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.