کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419096 | 681741 | 2014 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of colouring problems restricted to unichord-free and { square,unichord }-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A unichord in a graph is an edge that is the unique chord of a cycle. A square is an induced cycle on four vertices. A graph is unichord free if none of its edges is a unichord. We give a slight restatement of a known structure theorem for unichord-free graphs and use it to show that, with the only exception of the complete graph K4K4, every square-free, unichord-free graph of maximum degree 3 can be total-coloured with four colours. Our proof can be turned into a polynomial-time algorithm that actually outputs the colouring. This settles the class of square-free, unichord-free graphs as a class for which edge-colouring is NP-complete but total-colouring is polynomial.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 164, Part 1, 19 February 2014, Pages 191–199
Journal: Discrete Applied Mathematics - Volume 164, Part 1, 19 February 2014, Pages 191–199
نویسندگان
Raphael C.S. Machado, Celina M.H. de Figueiredo, Nicolas Trotignon,