A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs

Abstract

For a positive integer $k$, a $k$-colouring of a graph $G=(V,E)$ is a mapping $c:V\to \{1,2,...,k\}$ such that $c(u)\ne c(v)$ whenever $uv\in E$. The Colouring problem is to decide, for a given $G$ and $k$, whether a $k$-colouring of $G$ exists. If $k$ is fixed (that is, it is not part of the input), we have the decision problem $k$-Colouring instead. We survey known results on the computational complexity of Colouring and $k$-Colouring for graph classes that are characterized by one or two forbidden induced subgraphs. We also consider a number of variants: for example, where the problem is to extend a partial colouring, or where lists of permissible colours are given for each vertex.

References in corpus (12)

• Three-coloring graphs with no induced seven-vertex path II : using a triangle
• Three-coloring graphs with no induced seven-vertex path I : the triangle-free case
• A certifying algorithm for 3-colorability of P5-free graphs
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Narrowing the Complexity Gap for Colouring ($C_s$,$P_t$)-Free Graphs
• 4-coloring $P_6$-free graphs with no induced 5-cycles
• Bounding the Clique-Width of $H$-free Chordal Graphs
• Obstructions for three-coloring graphs without induced paths on six vertices
• Polynomial-time algorithms for minimum weighted colorings of ($P_5,{\bar{P}}_5$)-free graphs and related graph classes
• On color-critical ($P_5,{\overline{P}}_5$)-free graphs
• Exhaustive generation of $k$-critical $\mathcal{H}$-free graphs
• A Coloring Algorithm for $4K_1$-free line graphs

Cited by in corpus (7)

• Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Narrowing the Complexity Gap for Colouring ($C_s$,$P_t$)-Free Graphs
• 4-coloring $P_6$-free graphs with no induced 5-cycles
• Obstructions for three-coloring graphs without induced paths on six vertices
• Exhaustive generation of $k$-critical $\mathcal{H}$-free graphs
• Colourings, Homomorphisms, and Partitions of Transitive Digraphs