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.
@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}, zbl = {0923.05034}, mrnumber = {2000f:05051}, language = {en}, url = {https://aif.centre-mersenne.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 - https://aif.centre-mersenne.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 https://aif.centre-mersenne.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, Volume 49 (1999) no. 3, pp. 783-786. doi : 10.5802/aif.1691. https://aif.centre-mersenne.org/articles/10.5802/aif.1691/
[1] Hypergraphs, Combinatorics of finite sets, North-Holland, Amsterdam, New York, 1989.
,[2] On the optimal transversals of the odd cycles, Discrete Math., 169 (1997), 169-176. | MR | Zbl
, ,[3] Optimal packings of edge disjoint odd cycles, to appear. | Zbl
, ,[4] Hajós'Graph Coloring Conjecture, J. of Combinat. Theory, B26 (1979), 268-274. | MR | Zbl
,[5] Une classe d'hypergraphes bichromatiques, Discrete Math., 2 (1979), 407-410 (see also [1], p. 156). | MR | Zbl
, ,[6] Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2 (1972), 253-267. | MR | Zbl
,[7] Private communication.
,[8] Mango and Blueberries (to appear).
,[9] 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] On the presence of disjoint subgraphs of a specified type, J. of Graph Theory, 12 (1988), 101-111. | MR | Zbl
,[11] Graph coloring problems, Wiley Interscience, 1995. | MR | Zbl
, ,Cited by Sources: