Narrowing the Complexity Gap for Colouring (C s ,P t )-Free Graphs

DOI10.1007/978-3-319-07956-1_15zbMath1445.68110arXiv1407.1480OpenAlexW2264406464MaRDI QIDQ5251642

Matthew Johnson, Daniël Paulusma, Shenwei Huang

Publication date: 20 May 2015

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.1480

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Related Items

Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs, Approximately coloring graphs without long induced paths, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, On 3-coloring of \((2P_4,C_5)\)-free graphs, On 3-coloring of \((2P_4,C_5)\)-free graphs, Colouring square-free graphs without long induced paths