New Tools for Graph Coloring
From MaRDI portal
Publication:3088076
DOI10.1007/978-3-642-22935-0_1zbMath1343.68104OpenAlexW1947552815MaRDI QIDQ3088076
Publication date: 17 August 2011
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_1
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
Fair Colorful k-Center Clustering ⋮ The Densest $k$-Subhypergraph Problem ⋮ Unnamed Item ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ The Small Set Vertex expansion problem ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Finding Pseudorandom Colorings of Pseudorandom Graphs ⋮ Fair colorful \(k\)-center clustering
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Convex Relaxations and Integrality Gaps
- New approximation guarantee for chromatic number
- Conditional hardness for approximate coloring
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Subexponential Algorithms for Unique Games and Related Problems
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Forbidden Intersections
- Improving the performance guarantee for approximate graph coloring
- Approximate graph coloring by semidefinite programming
- Cones of Matrices and Set-Functions and 0–1 Optimization
- New approximation algorithms for graph coloring
- Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
This page was built for publication: New Tools for Graph Coloring