On the parameterized complexity of coloring graphs in the absence of a linear forest
type: Item
instance of: scholarly article
title: On the parameterized complexity of coloring graphs in the absence of a linear forest
zbMATH Open document ID: 1247.68108
author: Jean-François Couturier
author: Petr A. Golovach
author: Dieter Kratsch
author: Daniël Paulusma
published in: Journal of Discrete Algorithms
publication date: 2012-09-13T00:00:00Z
full work available at URL: 10695.pdf
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6082063
zbMATH Keywords: \(k\)-coloring
zbMATH Keywords: list \(k\)-coloring
zbMATH Keywords: \(H\)-free
zbMATH Keywords: linear forest
zbMATH Keywords: fixed-parameter tractable
MaRDI profile type: Publication
OpenAlex ID: W2050924495
cites work: On graphs with polynomially solvable maximum-weight clique problem
cites work: Q5422499
cites work: Three Complexity Results on Coloring P k -Free Graphs
cites work: Updating the complexity status of coloring graphs without a fixed induced linear forest
cites work: Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
cites work: A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
cites work: List Coloring in the Absence of a Linear Forest
cites work: Colouring Vertices of Triangle-Free Graphs
cites work: Q4393480
cites work: 4-Coloring H-Free Graphs When H Is Small
cites work: Q3216686
cites work: Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
cites work: The NP-Completeness of Edge-Coloring
cites work: Generalized coloring for tree-like graphs
cites work: Q3558598
cites work: Q5755526
cites work: Q4448764
cites work: Q4838453
cites work: On the complexity of 4-coloring graphs without long induced paths
cites work: NP completeness of finding the chromatic index of regular graphs
cites work: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
cites work: Q5710169
cites work: 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
cites work: Vertex colouring and forbidden subgraphs -- a survey
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: Graph colorings with local constraints -- a survey
cites work: The complexity of coloring graphs without long induced paths
DOI: 10.1016/J.JDA.2012.04.008
description: scientific article; zbMATH DE number 6082063