Gaspers, Serge and Huang, Shenwei and Paulusma, Daniël (2019) 'Colouring square-free graphs without long induced paths.', Journal of computer and system sciences., 106 . pp. 60-79.
The complexity of Colouring is fully understood for H-free graphs, but there are still major complexity gaps if two induced subgraphs and are forbidden. Let be the s-vertex cycle and be the t-vertex path . We show that Colouring is polynomial-time solvable for and , strengthening several known results. Our main approach is to initiate a study into the boundedness of the clique-width of atoms (graphs with no clique cutset) of a hereditary graph class. As a complementary result we prove that Colouring is NP-complete for and , which is the first hardness result on Colouring for -free graphs. Combining our new results with known results leads to an almost complete dichotomy for Colouring restricted to -free graphs.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (497Kb)
|Publisher Web site:||https://doi.org/10.1016/j.jcss.2019.06.002|
|Publisher statement:||© 2019 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|Date accepted:||22 June 2019|
|Date deposited:||02 July 2019|
|Date of first online publication:||28 June 2019|
|Date first made open access:||28 June 2020|
Save or Share this output
|Look up in GoogleScholar|