On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size

DOI10.1134/S1990478918040166zbMath1438.05105OpenAlexW2902303909WikidataQ128854192 ScholiaQ128854192MaRDI QIDQ4973236

Dmitrii V. Sirotkin, Dmitriy S. Malyshev

Publication date: 2 December 2019

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1990478918040166

zbMATH Keywords

computational complexityhereditary class3-colorability problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (5)

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ An intractability result for the vertex 3-colourability problem ⋮ 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 ⋮ Colouring graphs of bounded diameter in the absence of small cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex coloring of graphs with few obstructions
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Coloring graphs characterized by a forbidden subgraph
• The coloring problem for classes with two small obstructions
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Two complexity results for the vertex coloring problem
• 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
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• 4-coloring \(H\)-free graphs when \(H\) is small
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• Polynomial-time approximation algorithms for the coloring problem in some cases
• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
• Two cases of polynomial-time solvability for the coloring problem

This page was built for publication: On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size