Retour

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.

, 12 pages

Axes de recherche

Applications de recherche