Finding Pseudorandom Colorings of Pseudorandom Graphs

DOI10.4230/LIPIcs.FSTTCS.2017.37zbMath1498.68207OpenAlexW2789558393MaRDI QIDQ5136329

Madhur Tulsiani, Anand Louis, Akash Kumar

Publication date: 25 November 2020

Full work available at URL: http://dblp.uni-trier.de/db/conf/fsttcs/fsttcs2017.html#KumarLT17

zbMATH Keywords

graph coloringexpandersspectral algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• New approximation guarantee for chromatic number
• Coloring 3-colorable graphs with o(n 1/5 ) colors
• New Tools for Graph Coloring
• Subexponential Algorithms for Unique Games and Related Problems
• Conditional Hardness for Approximate Coloring
• Improving the performance guarantee for approximate graph coloring
• Approximate graph coloring by semidefinite programming
• New approximation algorithms for graph coloring
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Coloring Random and Semi-Random k-Colorable Graphs
• On the effect of randomness on planted 3-coloring models

This page was built for publication: Finding Pseudorandom Colorings of Pseudorandom Graphs