Improving the performance guarantee for approximate graph coloring

From MaRDI portal
Publication:3763600

DOI10.1145/2157.2158zbMath0627.68057OpenAlexW1982506822WikidataQ29399072 ScholiaQ29399072MaRDI QIDQ3763600

Avi Wigderson

Publication date: 1983

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2157.2158




Related Items (36)

CLAP: A New Algorithm for Promise CSPsEfficient Vertex- and Edge-Coloring of Outerplanar GraphsAn \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphsMatrix Relaxations in Combinatorial OptimizationOn the Complexity of Scheduling to Optimize Average Response TimeOn the complexity of H-coloringLocal-Global Phenomena in GraphsRandomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-functionAn on-line graph coloring algorithm with sublinear performance ratioUnnamed ItemRobust Factorizations and Colorings of Tensor GraphsSuper-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long CodesHardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ ColorsDistributed algorithms for maximum cliquesA better performance guarantee for approximate graph coloringThe smallest hard-to-color graphColoring bipartite hypergraphsApproximating maximum independent sets by excluding subgraphsLinear Index Coding via Semidefinite ProgrammingA still better performance guarantee for approximate graph coloringThe greedy algorithm is optimal for on-line edge coloringA simple algorithm for 4-coloring 3-colorable planar graphsApproximating maximum independent sets by excluding subgraphsGraph theory (algorithmic, algebraic, and metric problems)Unnamed ItemApproximating \(k\)-forest with resource augmentation: a primal-dual approachThe allocation problem in hardware designNew Tools for Graph ColoringThree-quarter approximation for the number of unused colors in graph coloringCombinatorial optimization in system configuration designUnnamed ItemWorst case analysis of a graph coloring algorithmHardness of Rainbow Coloring HypergraphsFinding Pseudorandom Colorings of Pseudorandom GraphsThe maximum clique problemDecomposing a set of points into chains, with applications to permutation and circle graphs




This page was built for publication: Improving the performance guarantee for approximate graph coloring