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


Stable Sets and Chromatic Number


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