2026-08-17T10:50:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8492 2024-03-06T10:42:20Z ddc:004 open_access

Colouring Square-Free Graphs without Long Induced Paths Gaspers, Serge Huang, Shenwei Paulusma, Daniel graph colouring hereditary graph class clique-width cycle path The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a given integer k such that no two adjacent vertices are coloured alike. The complexity of Colouring is fully understood for graph classes characterized by one forbidden induced subgraph H. Despite a huge body of existing work, there are still major complexity gaps if two induced subgraphs H_1 and H_2 are forbidden. We let H_1 be the s-vertex cycle C_s and H_2 be the t-vertex path P_t. We show that Colouring is polynomial-time solvable for s=4 and t<=6, which unifies several known results for Colouring on (H_1,H_2)-free graphs. Our algorithm is based on a novel decomposition theorem for (C_4,P_6)-free graphs without clique cutsets into homogeneous pairs of sets and a new framework for bounding the clique-width of a graph by the clique-width of its subgraphs induced by homogeneous pairs of sets. To apply this framework, we also need to use divide-and-conquer to bound the clique-width of subgraphs induced by homogeneous pairs of sets. To complement our positive result we also prove that Colouring is NP-complete for s=4 and t>=9, which is the first hardness result on Colouring for (C_4,P_t)-free graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Serge Gaspers and Shenwei Huang and Daniel Paulusma 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.35 urn:nbn:de:0030-drops-84922 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.35 eng https://creativecommons.org/licenses/by/3.0/legalcode