کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4652961 1632602 2007 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Claw-free circular-perfect graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Claw-free circular-perfect graphs
چکیده انگلیسی

The circular chromatic number of a graph is a well-studied refinement of the chromatic number. Circular-perfect graphs is a superclass of perfect graphs defined by means of this more general coloring concept. This paper studies claw-free circular-perfect graphs. A consequence of the strong perfect graph theorem is that minimal circular-imperfect graphs G have min{α(G),ω(G)}=2. In contrast to this result, it is shown in [Z. Pan and X. Zhu. Minimal circular-imperfect graphs of large clique number and large independence number. manuscript, 2006] that minimal circular-imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. We prove that claw-free minimal circular-imperfect graphs G have min{α(G),ω(G)}⩽3.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 29, 15 August 2007, Pages 451-455