The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
From MaRDI portal
Publication:2352049
DOI10.1016/j.disc.2015.04.019zbMath1315.05061OpenAlexW1012466235MaRDI QIDQ2352049
Publication date: 29 June 2015
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2015.04.019
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ An intractability result for the vertex 3-colourability problem ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Complexity classification of the edge coloring problem for a family of graph classes ⋮ The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Two complexity results for the vertex coloring problem ⋮ Critical hereditary graph classes: a survey ⋮ On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
Cites Work
- Vertex coloring of graphs with few obstructions
- The coloring problem for classes with two small obstructions
- Boundary properties of graphs for algorithmic graph problems
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Colouring vertices of triangle-free graphs without forests
- The strong perfect graph theorem
- The ellipsoid method and its consequences in combinatorial optimization
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- 4-coloring \(H\)-free graphs when \(H\) is small
- Boundary classes of graphs for the dominating set problem
- NP-hard graph problems and boundary classes of graphs
- List coloring in the absence of two subgraphs
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
- Two cases of polynomial-time solvability for the coloring problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item