List coloring in the absence of a linear forest
From MaRDI portal
Publication:2258070
DOI10.1007/s00453-013-9777-0zbMath1307.05068OpenAlexW2089686090MaRDI QIDQ2258070
Daniël Paulusma, Dieter Kratsch, Jean-François Couturier, Petr A. Golovach
Publication date: 2 March 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/10688/1/10688.pdf
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Coloring problems on bipartite graphs of small diameter ⋮ Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ 3-colouring \(P_t\)-free graphs without short odd cycles ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Connected vertex cover for \((sP_1+P_5)\)-free graphs ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ Colouring (P_r+P_s)-Free Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
- Some new hereditary classes where graph coloring remains NP-hard
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Colouring vertices of triangle-free graphs without forests
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Dominating cliques in \(P_ 5\)-free graphs
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Vertex colouring and forbidden subgraphs -- a survey
- On the complexity of 4-coloring graphs without long induced paths
- 4-Coloring H-Free Graphs When H Is Small
- Three Complexity Results on Coloring P k -Free Graphs
- A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
- The NP-Completeness of Edge-Coloring
- Graph colorings with local constraints -- a survey
- NP completeness of finding the chromatic index of regular graphs
This page was built for publication: List coloring in the absence of a linear forest
