A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions

DOI10.15507/2079-6900.22.202001.38-47OpenAlexW3013337024MaRDI QIDQ6143681

Dmitriy S. Malyshev

Publication date: 24 January 2024

Published in: Zhurnal Srednevolzhskogo Matematicheskogo Obshchestva (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/svmo759

zbMATH Keywords

polynomial-time algorithmhereditary graph classvertex 3-colourability problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ An intractability result for the vertex 3-colourability problem

Cites Work

• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• 4-coloring \(H\)-free graphs when \(H\) is small
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
• On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
• Four-coloring P₆-free graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions