New tools for graph coloring

DOI10.1007/978-3-642-22935-0_1MaRDI QIDQ3088076zbMATH OpenOpenAlexFDO

Authors Rong Ge, Sanjeev Arora

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

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Approximate graph coloring by semidefinite programming
• Approximate hypergraph coloring
• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
• Coloring 3-colorable graphs with \(o(n^{1/5})\) colors
• CSP gaps and reductions in the lasserre hierarchy

Cites work

• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 1757962 (Why is no real title available?)
• scientific article; zbMATH DE number 3341050 (Why is no real title available?)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Approximate graph coloring by semidefinite programming
• Conditional hardness for approximate coloring
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Convex relaxations and integrality gaps
• Forbidden Intersections
• Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
• Improving the performance guarantee for approximate graph coloring
• Linear degree extractors and the inapproximability of max clique and chromatic number
• New approximation algorithms for graph coloring
• New approximation guarantee for chromatic number
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Subexponential algorithms for unique games and related problems

Cited in

(9)

• Fair colorful \(k\)-center clustering
• Fair colorful \(k\)-center clustering
• The densest \(k\)-subhypergraph problem
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
• The small set vertex expansion problem
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• A new color change to improve the coloring of a graph
• Robust Factorizations and Colorings of Tensor Graphs

This page was built for publication: New tools for graph coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088076)