We introduce a new concept of chromatic number for directed graphs, called the colour number and use it to upper bound the transitive clique number and the Sperner capacity of arbitrary directed graphs. Our results represent a common generalization of previous bounds of Alon and the second author and lead to a concept of perfectness for directed graphs.
Colour number, capacity and perfectness of directed graphs / Fachini, Emanuela; Korner, Janos. - In: GRAPHS AND COMBINATORICS. - ISSN 0911-0119. - STAMPA. - 16:(2000), pp. 389-398. [10.1007/PL00007226]
Colour number, capacity and perfectness of directed graphs.
FACHINI, Emanuela;KORNER, JANOS
2000
Abstract
We introduce a new concept of chromatic number for directed graphs, called the colour number and use it to upper bound the transitive clique number and the Sperner capacity of arbitrary directed graphs. Our results represent a common generalization of previous bounds of Alon and the second author and lead to a concept of perfectness for directed graphs.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
