Two cases of polynomial-time solvability for the coloring problem
From MaRDI portal
Publication:5963654
Recommendations
- Polynomial cases for the vertex coloring problem
- The coloring problem for classes with two small obstructions
- Polynomial-time approximation algorithms for the coloring problem in some cases
- scientific article; zbMATH DE number 2044943
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
Cites work
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 6460018 (Why is no real title available?)
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
- Boundary properties of graphs for algorithmic graph problems
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- 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
- List coloring in the absence of two subgraphs
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Some new hereditary classes where graph coloring remains NP-hard
- Sur le coloriage des graphs
- The coloring problem for classes with two small obstructions
- Vertex coloring of graphs with few obstructions
Cited in
(29)- The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
- Deciding Relaxed Two-Colourability: A Hardness Jump
- Colouring square-free graphs without long induced paths
- The coloring problem for classes with two small obstructions
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
- Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
- Polynomial-time approximation algorithms for the coloring problem in some cases
- A note on the Cornaz-Jost transformation to solve the graph coloring problem
- Colouring square-free graphs without long induced paths
- Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions
- Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
- Colouring diamond-free graphs
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- Critical hereditary graph classes: a survey
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
- The chromatic number of (\(P_5\), HVN)-free graphs
- Coloring graphs without induced \(P_5\) or \(K_5-e\)
- A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
- Clique-width of graph classes defined by two forbidden induced subgraphs
- Two complexity results for the vertex coloring problem
- scientific article; zbMATH DE number 7589530 (Why is no real title available?)
- Non-perfect \((P_5, C_5, K_5 -e)\)-free graphs are 5-colorable
- Polynomial cases for the vertex coloring problem
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- Divisibility and coloring of some \(P_5\)-free graphs
This page was built for publication: Two cases of polynomial-time solvability for the coloring problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963654)
