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

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},
     pages = {783--786},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {49},
     number = {3},
     year = {1999},
     doi = {10.5802/aif.1691},
     mrnumber = {2000f:05051},
     zbl = {0923.05034},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/aif.1691/}
}
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
SP  - 783
EP  - 786
VL  - 49
IS  - 3
PB  - Association des Annales de l’institut Fourier
UR  - http://www.numdam.org/articles/10.5802/aif.1691/
DO  - 10.5802/aif.1691
LA  - en
ID  - AIF_1999__49_3_783_0
ER  - 
%0 Journal Article
%A Berge, Claude
%A Reed, Bruce
%T Edge-disjoint odd cycles in graphs with small chromatic number
%J Annales de l'Institut Fourier
%D 1999
%P 783-786
%V 49
%N 3
%I Association des Annales de l’institut Fourier
%U http://www.numdam.org/articles/10.5802/aif.1691/
%R 10.5802/aif.1691
%G en
%F 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) no. 3, pp. 783-786. doi : 10.5802/aif.1691. http://www.numdam.org/articles/10.5802/aif.1691/

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

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

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

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

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

[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

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

[11] B. Toft, T.R. Jensen, Graph coloring problems, Wiley Interscience, 1995. | MR | Zbl

Cité par Sources :