Colouring diamond-free graphs

作者：

Highlights：

• We classify the complexity of Colouring for (diamond, H)-free graphs when |V(H)|≤5.

• We generalize a known decomposition of bipartite graphs to k-partite graphs.

• We find five new classes of (H1,H2)-free graphs of bounded clique-width.

• This reduces the number of open cases from 13 to 8.

摘要

•We classify the complexity of Colouring for (diamond, H)-free graphs when |V(H)|≤5.•We generalize a known decomposition of bipartite graphs to k-partite graphs.•We find five new classes of (H1,H2)-free graphs of bounded clique-width.•This reduces the number of open cases from 13 to 8.

论文关键词：Graph colouring,Diamond-free,Clique-width,Forbidden induced subgraph

论文评审过程：Received 16 January 2017, Accepted 5 June 2017, Available online 22 June 2017, Version of Record 7 August 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.06.005