Polynomial-time approximation algorithms for the coloring problem in some cases
From MaRDI portal
Publication:2359789
DOI10.1007/s10878-016-0008-xzbMath1367.05078OpenAlexW2298538966MaRDI QIDQ2359789
Publication date: 22 June 2017
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-016-0008-x
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
The weighted coloring problem for two graph classes characterized by small forbidden induced structures ⋮ 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 ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ The intersection of two vertex coloring problems ⋮ On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
Cites Work
