2026-08-17T08:20:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9953 2026-05-27T12:59:45Z ddc:004 open_access

Colouring (P_r+P_s)-Free Graphs Klimošová, Tereza Malík, Josef Masařík, Tomáš Novotná, Jana Paulusma, Daniël Slívová, Veronika vertex colouring H-free graph linear forest 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tereza Klimošová and Josef Malík and Tomáš Masařík and Jana Novotná and Daniël Paulusma and Veronika Slívová 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.5 urn:nbn:de:0030-drops-99533 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.5 eng https://creativecommons.org/licenses/by/3.0/legalcode