کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777677 | 1632971 | 2017 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Colouring perfect graphs with bounded clique number
ترجمه فارسی عنوان
رنگ کامل نمودارها با تعداد سلول محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم رنگ آمیزی، گراف کامل پارتیشن شکسته متعادل،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
In this paper we first give a polynomial-time algorithm that, with input a perfect graph, outputs a balanced skew partition if there is one. Then we use this to obtain a combinatorial algorithm that finds an optimal colouring of a perfect graph with clique number k, in time that is polynomial for fixed k.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 757-775
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 757-775
نویسندگان
Maria Chudnovsky, Aurélie Lagoutte, Paul Seymour, Sophie Spirkl,