New tools for graph coloring

DOI10.1007/978-3-642-22935-0_1zbMATH Open1343.68104OpenAlexW1947552815MaRDI QIDQ3088076FDOQ3088076

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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
• Title not available (Why is that?)
• 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)