Colour number, capacity, and perfectness of directed graphs (Q5935600): Difference between revisions

The authors introduce a variant of the chromatic number for a directed graph \(G\), called the colour number: the minimum, over all partitions of \(V(G)\), of the sum (taken over all subsets of the partition) of the quantities: 1 plus the maximum outdegree of the directed graph induced by a given subset. This parameter is used to upper-bound the transitive clique number and the Sperner capacity of arbitrary directed graphs. The results give a common generalization of previously known bounds and lead to a concept of perfectness for a directed graph: the colour number and the transitive clique number agree, for each induced subgraph.