文章基本信息

标题：Colouring (P_r+P_s)-Free Graphs
本地全文：下载
作者：Tereza Klimosov{\'a ; Josef Mal{\'i}k ; Tom{\'a}s Masar{\'i}k 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：123
页码：1-13
DOI：10.4230/LIPIcs.ISAAC.2018.5
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list L(u) subseteq {1,...,k}, then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. We prove that List 3-Colouring is polynomial-time solvable for (P_2+P_5)-free graphs and for (P_3+P_4)-free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices. We also prove that 5-Colouring is NP-complete for (P_3+P_5)-free graphs.
关键词：vertex colouring; H-free graph; linear forest