Voir la notice de l'article provenant de la source Numdam
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},
mrnumber = {2000f:05051},
zbl = {0923.05034},
language = {en},
url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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
Cité par Sources :