4-coloring \(H\)-free graphs when \(H\) is small
type: Item
instance of: scholarly article
title: 4-coloring \(H\)-free graphs when \(H\) is small
zbMATH Open document ID: 1259.05061
author: Petr A. Golovach
author: Daniël Paulusma
author: Jian Song
published in: Discrete Applied Mathematics
publication date: 2012-11-22T00:00:00Z
review text: The paper determines the computational complexity of \(4\)-colouring \(H\)-free graphs where \(H\) is a graph on at most five vertices. The \(k\)-colouring problem is to decide whether a given graph has a \(k\)-colouring. Here \(k\) is fixed, that is, it is not part of the input. The \(k\)-colouring problem is \(NP\)-complete for any fixed \(k \geq 3\); however, the problem is polynomial-time solvable when restricted to certain graph classes. A graph is said to be \(H\)-free if it contains no induced subgraph isomorphic to \(H\). \textit{V. V. Lozin} and \textit{M. Kamiński} [Contrib. Discrete Math. 2, No. 1, 61--66 (2007; Zbl 1188.05065)] proved that, for \(k \geq 3\), the \(k\)-colouring problem is \(NP\)-complete for the class of \(H\)-free graphs whenever \(H\) contains a cycle, while \textit{D. Leven} and \textit{Z. Galil} [J.\ Algorithms 4, 35--44 (1983; Zbl 0509.68037)] proved that the same conclusion holds whenever \(H\) is a forest with a vertex of degree at least three. This leaves the question of the computational complexity of the \(k\)-colouring problem when restricted to \(H\)-free graphs where \(H\)-is a linear forest, that is, a disjoint union of paths. Through a series of previous papers, it has been proved that, for any graph \(H\) on at most six vertices, the \(3\)-colouring problem is polynomial-time solvable on \(H\)-free graphs whenever \(H\) is a linear forest, and \(NP\)-complete otherwise. In the paper under review it is proved that, for any fixed graph \(H\) on at most five vertices, the \(5\)-colouring problem is polynomial-time solvable on \(H\)-free graphs whenever \(H\) is a linear forest, and \(NP\)-complete otherwise.
reviewed by: Anders Sune Pedersen
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6109939
zbMATH Keywords: graph coloring
zbMATH Keywords: forbidden induced subgraph
zbMATH Keywords: linear forest
zbMATH Keywords: polynomial-time algorithm
MaRDI profile type: Publication
full work available at URL: j.dam.2012.08.022
OpenAlex ID: W1565326817
DOI: 10.1016/J.DAM.2012.08.022
Recommended article: 4-Coloring H-Free Graphs When H Is Small
Recommended article: Coloring Graphs Characterized by a Forbidden Subgraph
Recommended article: Coloring graphs characterized by a forbidden subgraph
Recommended article: Updating the complexity status of coloring graphs without a fixed induced linear forest
Recommended article: Classifying \(k\)-edge colouring for \(H\)-free graphs
Recommended article: Colouring (P_r+P_s)-Free Graphs
Recommended article: Colouring Vertices of Triangle-Free Graphs
Recommended article: Colouring \((P_r + P_s)\)-free graphs
Recommended article: Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
Recommended article: On 3-coloring of \((2P_4,C_5)\)-free graphs
description: scientific article; zbMATH DE number 6109939