G-2001-11
Stable Sets and Chromatic Number
et référence BibTeX
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.
Paru en février 2001 , 12 pages