Closing complexity gaps for coloring problems on \(H\)-free graphs
From MaRDI portal
Publication:2252529
DOI10.1016/j.ic.2014.02.004zbMath1295.05105OpenAlexW1974068132MaRDI QIDQ2252529
Daniël Paulusma, Jian Song, Petr A. Golovach
Publication date: 18 July 2014
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2014.02.004
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (26)
Solving Problems on Graphs of High Rank-Width ⋮ Boundary classes for graph problems involving non-local properties ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring ⋮ Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring ⋮ Unnamed Item ⋮ List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\) ⋮ Non-empty intersection of longest paths in \(H\)-free graphs ⋮ Solving problems on graphs of high rank-width ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ List 3-coloring graphs with no induced \(P_6 + rP_3\) ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Unnamed Item ⋮ 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 ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Parameterized coloring problems on chordal graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Some results concerning the complexity of restricted colorings of graphs
- Generalized coloring for tree-like graphs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Parameterized complexity of vertex colouring
- Vertex colouring and forbidden subgraphs -- a survey
- Three complexity results on coloring \(P_k\)-free graphs
- 3-colouring AT-free graphs in polynomial time
- Precoloring extension on unit interval graphs
- Improved Complexity Results on k-Coloring P t -Free Graphs
- 4-Coloring H-Free Graphs When H Is Small
- Colouring AT-Free Graphs
- Data Reduction for Graph Coloring Problems
- List Coloring in the Absence of a Linear Forest
- Graph colorings with local constraints -- a survey
- Independent Sets in Asteroidal Triple-Free Graphs
- The complexity of satisfiability problems
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Exploring the complexity boundary between coloring and list-coloring
This page was built for publication: Closing complexity gaps for coloring problems on \(H\)-free graphs
