Edge-disjoint odd cycles in graphs with small chromatic number
Annales de l'Institut Fourier, Volume 49 (1999) no. 3, p. 783-786

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.

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.

     author = {Berge, Claude and Reed, Bruce},
     title = {Edge-disjoint odd cycles in graphs with small chromatic number},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {49},
     number = {3},
     year = {1999},
     pages = {783-786},
     doi = {10.5802/aif.1691},
     zbl = {0923.05034},
     mrnumber = {2000f:05051},
     language = {en},
     url = {http://www.numdam.org/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, Volume 49 (1999) no. 3, pp. 783-786. doi : 10.5802/aif.1691. http://www.numdam.org/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