Gaspers, Serge ;
Huang, Shenwei ;
Paulusma, Daniel
Colouring SquareFree Graphs without Long Induced Paths
Abstract
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 svertex cycle C_s and H_2 be the tvertex path P_t. We show that Colouring is polynomialtime 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 cliquewidth of a graph by the cliquewidth of its subgraphs induced by homogeneous pairs of sets. To apply this framework, we also need to use divideandconquer to bound the cliquewidth of subgraphs induced by homogeneous pairs of sets. To complement our positive result we also prove that Colouring is NPcomplete for s=4 and t>=9, which is the first hardness result on Colouring for (C_4,P_t)free graphs.
BibTeX  Entry
@InProceedings{gaspers_et_al:LIPIcs:2018:8492,
author = {Serge Gaspers and Shenwei Huang and Daniel Paulusma},
title = {{Colouring SquareFree Graphs without Long Induced Paths}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {35:135:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8492},
URN = {urn:nbn:de:0030drops84922},
doi = {10.4230/LIPIcs.STACS.2018.35},
annote = {Keywords: graph colouring, hereditary graph class, cliquewidth, cycle, path}
}
27.02.2018
Keywords: 

graph colouring, hereditary graph class, cliquewidth, cycle, path 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

27.02.2018 