New Tools for Graph Coloring

DOI10.1007/978-3-642-22935-0_1zbMath1343.68104OpenAlexW1947552815MaRDI QIDQ3088076

Rong Ge

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

Mathematics Subject Classification ID

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