The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
From MaRDI portal
Publication:2409536
Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Recommendations
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- An intractability result for the vertex 3-colourability problem
- The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
- Polynomial cases for the vertex coloring problem
- Vertex coloring of graphs with few obstructions
Cites work
- 4-coloring \(H\)-free graphs when \(H\) is small
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Coloring edges and vertices of graphs without short or long cycles
- Coloring graphs characterized by a forbidden subgraph
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- scientific article; zbMATH DE number 2044943 (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 the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- 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
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Two cases of polynomial-time solvability for the 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
(13)- Classifying \(k\)-edge colouring for \(H\)-free graphs
- The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
- An intractability result for the vertex 3-colourability problem
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
- Colouring graphs of bounded diameter in the absence of small cycles
- Two cases of polynomial-time solvability for the coloring problem
- A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
- A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
- Polynomial cases for the vertex coloring problem
- Some classifications of the computational complexity for the vertex 3-colourability problem
- The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
- The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
This page was built for publication: The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409536)
