Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9516051 | Journal of Combinatorial Theory, Series B | 2005 | 17 Pages |
Abstract
We introduce a directed analog of the local chromatic number defined by ErdÅs et al. [Discrete Math. 59 (1986) 21-34] and show that it provides an upper bound for the Sperner capacity of a directed graph. Applications and variants of this result are presented. In particular, we find a special orientation of an odd cycle and show that it achieves the maximum of Sperner capacity among the differently oriented versions of the cycle. We show that apart from this orientation, for all the others an odd cycle has the same Sperner capacity as a single edge graph. We also show that the (undirected) local chromatic number is bounded from below by the fractional chromatic number while for power graphs the two invariants have the same exponential asymptotics (under the co-normal product on which the definition of Sperner capacity is based). We strengthen our bound on Sperner capacity by introducing a fractional relaxation of our directed variant of the local chromatic number.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
János Körner, Concetta Pilotto, Gábor Simonyi,