On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
DOI10.1134/S1990478918040166zbMATH Open1438.05105OpenAlexW2902303909WikidataQ128854192 ScholiaQ128854192MaRDI QIDQ4973236FDOQ4973236
Authors: Dmitrii V. Sirotkin, D. 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
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- 4-coloring \(H\)-free graphs when \(H\) is small
- The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
- Vertex coloring of graphs with few obstructions
- Title not available (Why is that?)
- The coloring problem for classes with two small obstructions
- Title not available (Why is that?)
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Coloring edges and vertices of graphs without short or long cycles
- Coloring graphs characterized by a forbidden subgraph
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Colouring vertices of triangle-free graphs without forests
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Two complexity results for the vertex coloring problem
- Two cases of polynomial-time solvability for the coloring problem
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- Polynomial-time approximation algorithms for the coloring problem in some cases
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
- A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
- Some new hereditary classes where graph coloring remains NP-hard
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)
