Groupe d’études et de recherche en analyse des décisions

# Stable Sets and Chromatic Number

## Dominique De Werra et Pierre Hansen

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.

, 12 pages