Colouring (sP₁+P₅)-Free Graphs: a Mim-Width Perspective

arXiv2004.05022MaRDI QIDQ6338474FDOQ6338474

Authors: Nick Brettell, Jake Horsfield, Daniël Paulusma 

Publication date: 10 April 2020

Abstract: We prove that the class of $(K_t,s{P}_1+P_5)$-free graphs has bounded mim-width for every $sgeq0$ and $tgeq1$, and that there is a polynomial-time algorithm that, given a graph in the class, computes a branch decomposition of constant mim-width. A large number of NP-complete graph problems become polynomial-time solvable on graph classes with bounded mim-width and for which a branch decomposition is quickly computable. The $k$-Colouring problem is an example of such a problem. For this problem, we may assume that the input graph is $K_{k+1}$-free. Then, as a consequence of our result, we obtain a new proof for the known result that for every fixed $kgeq1$ and $sgeq0$, $k$-Colouring is polynomial-time solvable for $(s{P}_1+P_5)$-free graphs. In fact, our findings show that the underlying reason for this polynomial-time algorithm is that the class has bounded mim-width.

This page was built for publication: Colouring $(sP_1+P_5)$-Free Graphs: a Mim-Width Perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6338474)