Two cases of polynomial-time solvability for the coloring problem
From MaRDI portal
Publication:5963654
DOI10.1007/s10878-014-9792-3zbMath1333.05120OpenAlexW2124367257MaRDI QIDQ5963654
Publication date: 23 February 2016
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-014-9792-3
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (20)
The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ Colouring diamond-free graphs ⋮ The weighted coloring problem for two graph classes characterized by small forbidden induced structures ⋮ The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs ⋮ 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 square-free graphs without long induced paths. ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes ⋮ Coloring graphs without induced \(P_5\) or \(K_5-e\) ⋮ Divisibility and coloring of some \(P_5\)-free graphs ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Polynomial cases for the vertex coloring problem ⋮ Two complexity results for the vertex coloring problem ⋮ Critical hereditary graph classes: a survey ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size ⋮ Colouring square-free graphs without long induced paths ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex coloring of graphs with few obstructions
- Colouring of graphs with Ramsey-type forbidden subgraphs
- The coloring problem for classes with two small obstructions
- Boundary properties of graphs for algorithmic graph problems
- Some new hereditary classes where graph coloring remains NP-hard
- Colouring vertices of triangle-free graphs without forests
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
- List Coloring in the Absence of Two Subgraphs
- Sur le coloriage des graphs
This page was built for publication: Two cases of polynomial-time solvability for the coloring problem
