Geodesic
Sur les Ensembles de Sommets Indépendants Dans les Graphes Chromatiques Minimaux
Canadian journal of mathematics, Tome 21 (1969) no. 1, pp. 274-278

Voir la notice de l'article provenant de la source Cambridge University Press

f(n, k) sera l'entier maximum t tel qu'il existe un graphe G ayant les propriétés suivantes: (a) G possède n sommets; (b) le nombre chromatique de G est égal à k; (c) Gest minimal par rapport à la propriété (b); c'est-à-dire, la suppression ede n'importe quelle arête rend G(k – 1)-colorable; (d) il existe t sommets indépendants de G, c'est-à-dire dont nulle paire ne se joigne par une arête. Un graphe sera k-minimal s'il possède les propriétés (b) et (c). Puisque les graphes 3-minimaux sont tous des polygones impairs, il s'ensuit que f(n, 3) = [n/2] (n = 3, 5, 7, ...), Il y a quelque temps T. Gallai a posé la conjecture: 1.1 M. Simonovits a réfuté l'inégalité stricte dans (1.1) en prouvant que 1.2 
Brown, W. G.; Moon, J. W. Sur les Ensembles de Sommets Indépendants Dans les Graphes Chromatiques Minimaux. Canadian journal of mathematics, Tome 21 (1969) no. 1, pp. 274-278. doi: 10.4153/CJM-1969-028-5
@article{10_4153_CJM_1969_028_5,
     author = {Brown, W. G. and Moon, J. W.},
     title = {Sur les {Ensembles} de {Sommets} {Ind\'ependants} {Dans} les {Graphes} {Chromatiques} {Minimaux}},
     journal = {Canadian journal of mathematics},
     pages = {274--278},
     year = {1969},
     volume = {21},
     number = {1},
     doi = {10.4153/CJM-1969-028-5},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1969-028-5/}
}
TY  - JOUR
AU  - Brown, W. G.
AU  - Moon, J. W.
TI  - Sur les Ensembles de Sommets Indépendants Dans les Graphes Chromatiques Minimaux
JO  - Canadian journal of mathematics
PY  - 1969
SP  - 274
EP  - 278
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1969-028-5/
DO  - 10.4153/CJM-1969-028-5
ID  - 10_4153_CJM_1969_028_5
ER  - 
%0 Journal Article
%A Brown, W. G.
%A Moon, J. W.
%T Sur les Ensembles de Sommets Indépendants Dans les Graphes Chromatiques Minimaux
%J Canadian journal of mathematics
%D 1969
%P 274-278
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1969-028-5/
%R 10.4153/CJM-1969-028-5
%F 10_4153_CJM_1969_028_5

Cité par Sources :