کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9516051 1343756 2005 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Local chromatic number and Sperner capacity
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Local chromatic number and Sperner capacity
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 95, Issue 1, September 2005, Pages 101-117
نویسندگان
, , ,