Some classifications of the computational complexity for the vertex 3-colourability problem
From MaRDI portal
Cites work
- 4-coloring \(H\)-free graphs when \(H\) is small
- A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
- Coloring edges and vertices of graphs without short or long cycles
- Coloring Graphs with Constraints on Connectivity
- Coloring vertices of claw-free graphs in three colors
- Colouring \((P_r + P_s)\)-free graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Four-coloring \(P_6\)-free graphs
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 5179133 (Why is no real title available?)
- scientific article; zbMATH DE number 3043302 (Why is no real title available?)
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- On graphs with polynomially solvable maximum-weight clique problem
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- 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
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Updating the complexity status of coloring graphs without a fixed induced linear forest
This page was built for publication: Some classifications of the computational complexity for the vertex 3-colourability problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7309601)
