On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
From MaRDI portal
Publication:4973236
Recommendations
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- Vertex coloring of graphs with few obstructions
- An intractability result for the vertex 3-colourability problem
- Coloring graphs characterized by a forbidden subgraph
- Coloring graphs characterized by a forbidden subgraph
Cites work
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 3043302 (Why is no real title available?)
- 4-coloring \(H\)-free graphs when \(H\) is small
- Coloring edges and vertices of graphs without short or long cycles
- Coloring graphs characterized by a forbidden subgraph
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Colouring vertices of triangle-free graphs without forests
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Polynomial-time approximation algorithms for the coloring problem in some cases
- The coloring problem for classes with two small obstructions
- 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
- Two cases of polynomial-time solvability for the coloring problem
- Two complexity results for the vertex coloring problem
- 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
- Vertex coloring of graphs with few obstructions
Cited in
(12)- The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
- Vertex coloring of graphs with few obstructions
- A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
- Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
- The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
- Polynomial-time approximation algorithms for the coloring problem in some cases
- An intractability result for the vertex 3-colourability problem
- Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- Colouring graphs of bounded diameter in the absence of small cycles
- Some new hereditary classes where graph coloring remains NP-hard
- A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4973236)
