The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs

DOI10.1016/j.disc.2015.04.019zbMath1315.05061OpenAlexW1012466235MaRDI QIDQ2352049

Dmitriy S. Malyshev

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

zbMATH Keywords

computational complexitypolynomial-time algorithm3-colorability problem

Mathematics Subject Classification ID

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