Back

G-2001-11

Stable Sets and Chromatic Number

and

BibTeX reference

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

Research Axes

Research applications