کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650622 1632449 2006 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Kernels and perfectness in arc-local tournament digraphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Kernels and perfectness in arc-local tournament digraphs
چکیده انگلیسی

In this paper we give a characterization of kernel-perfect (and of critical kernel-imperfect) arc-local tournament digraphs. As a consequence, we prove that arc-local tournament digraphs satisfy a strenghtened form of the following interesting conjecture which constitutes a bridge between kernels and perfectness in digraphs, stated by C. Berge and P. Duchet in 1982: a graph G is perfect if and only if any normal orientation of G is kernel-perfect. We prove a variation of this conjecture for arc-local tournament orientable graphs. Also it is proved that normal arc-local tournament orientable graphs satisfy a stronger form of Berge's strong perfect graph conjecture.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issues 19–20, 6 October 2006, Pages 2473–2480
نویسندگان
,