کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874198 | 1441028 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On colouring (2P2,H)-free and (P5,H)-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On colouring (2P2,H)-free and (P5,H)-free graphs On colouring (2P2,H)-free and (P5,H)-free graphs](/preview/png/6874198.png)
چکیده انگلیسی
The Colouring problem asks whether the vertices of a graph can be coloured with at most k colours for a given integer k in such a way that no two adjacent vertices receive the same colour. A graph is (H1,H2)-free if it has no induced subgraph isomorphic to H1 or H2. A connected graph H1 is almost classified if Colouring on (H1,H2)-free graphs is known to be polynomial-time solvable or NP-complete for all but finitely many connected graphs H2. We show that every connected graph H1 apart from the claw K1,3 and the 5-vertex path P5 is almost classified. We also prove a number of new hardness results for Colouring on (2P2,H)-free graphs. This enables us to list all graphs H for which the complexity of Colouring is open on (2P2,H)-free graphs and all graphs H for which the complexity of Colouring is open on (P5,H)-free graphs. In fact we show that these two lists coincide. Moreover, we show that the complexities of Colouring for (2P2,H)-free graphs and for (P5,H)-free graphs are the same for all known cases.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 134, June 2018, Pages 35-41
Journal: Information Processing Letters - Volume 134, June 2018, Pages 35-41
نویسندگان
Konrad K. Dabrowski, Daniël Paulusma,