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

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
نویسندگان
, , ,