Edge-disjoint odd cycles in graphs with small chromatic number
Berge, Claude ; Reed, Bruce
Annales de l'Institut Fourier, Tome 49 (1999), p. 783-786 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

On considère pour un graphe simple le nombre minimum d’arêtes dont l’élimination détruit tous les cycles impairs, et le nombre maximum de cycles impairs qui sont disjoints au sens des arêtes. Quand ces deux coefficients sont égaux, le graphe présente des propriétés intéressantes en relation avec le nombre chromatique.

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.

@article{AIF_1999__49_3_783_0,
     author = {Berge, Claude and Reed, Bruce},
     title = {Edge-disjoint odd cycles in graphs with small chromatic number},
     journal = {Annales de l'Institut Fourier},
     volume = {49},
     year = {1999},
     pages = {783-786},
     doi = {10.5802/aif.1691},
     mrnumber = {2000f:05051},
     zbl = {0923.05034},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_1999__49_3_783_0}
}

Berge, Claude; Reed, Bruce. Edge-disjoint odd cycles in graphs with small chromatic number. Annales de l'Institut Fourier, Tome 49 (1999) pp. 783-786. doi : 10.5802/aif.1691. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_783_0/

[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. | MR 98c:05094 | Zbl 0883.05088

[3] C. Berge, B. Reed, Optimal packings of edge disjoint odd cycles, to appear. | Zbl 0945.05048

[4] P.C. Catlin, Hajós'Graph Coloring Conjecture, J. of Combinat. Theory, B26 (1979), 268-274. | MR 81g:05057 | Zbl 0385.05033

[5] J.-C. Fournier, M. Las Vergnas, Une classe d'hypergraphes bichromatiques, Discrete Math., 2 (1979), 407-410 (see also [1], p. 156). | MR 46 #5156 | Zbl 0247.05127

[6] L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2 (1972), 253-267. | MR 46 #1624 | Zbl 0239.05111

[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. | Zbl 0895.05034

[10] C. Thomassen, On the presence of disjoint subgraphs of a specified type, J. of Graph Theory, 12 (1988), 101-111. | MR 89e:05174 | Zbl 0662.05032

[11] B. Toft, T.R. Jensen, Graph coloring problems, Wiley Interscience, 1995. | MR 95h:05067 | Zbl 0855.05054