Stable sets and chromatic number

Dominique De Werra*, Ecole Polytechnique Fédérale de Lausanne et CERMSEM
Pierre Hansen**, GERAD

Résumé. On présente une généralisation du théorème de Roy-Gallai ; elle est basée sur l'existence dans tout graphe orienté d'un ensemble stable S tel que pour tout sommet w n'appartenant pas à S, il existe un chemin élémentaire d'un sommet v de S à w. La borne obtenue améliore des résultats antérieurs de Berge et de Li.
Mots clés : Coloration de graphes, nombre chromatique, ensemble stable, plus long chemin.

Abstract. A generalization of the Roy-Gallai theorem is presented : it is based on the existence in any oriented graph of a stable set S such that for any node w not in S there is an elementary path from some node of S to w. The bound obtained improves earlier results by Berge and by Li.
Keywords : Graph coloring, chromatic number, stable set, longest path.

*Département de Mathématiques, Ecole Polytechnique Fédérale de Lausanne, CH-1015 Lausanne.
**GERAD and Département des Méthodes Quantitatives de Gestion, Ecole des Hautes Etudes Commerciales, Montréal (Canada).