A Spectral Technique for Coloring Random 3-Colorable Graphs

DOI10.1137/S0097539794270248zbMath0884.05042OpenAlexW2079035346MaRDI QIDQ4376197

Noga Alon, Nabil Kahale

Publication date: 10 February 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794270248

zbMATH Keywords

algorithmsgraph coloringrandom graphsgraph eigenvalues

Mathematics Subject Classification ID

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

Related Items (38)

Structural similarity: spectral methods for relaxed blockmodeling ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Expected complexity of graph partitioning problems ⋮ Information-theoretic thresholds from the cavity method ⋮ Cheeger Inequalities for General Edge-Weighted Directed Graphs ⋮ Universal completability, least eigenvalue frameworks, and vector colorings ⋮ Message passing algorithms for MLS-3LIN problem ⋮ Constructing uniquely realizable graphs ⋮ Random perturbation of low rank matrices: improving classical bounds ⋮ Unnamed Item ⋮ A Simple SVD Algorithm for Finding Hidden Partitions ⋮ On the security of Goldreich's one-way function ⋮ A Spectral Method for MAX2SAT in the Planted Solution Model ⋮ Metric uniformization and spectral bounds for graphs ⋮ On the Random Satisfiable Process ⋮ A Spectral Approach to Analysing Belief Propagation for 3-Colouring ⋮ Graph Partitioning via Adaptive Spectral Techniques ⋮ A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming ⋮ Coloring bipartite hypergraphs ⋮ Community Detection and Stochastic Block Models ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Complexity analysis of a decentralised graph colouring algorithm ⋮ Why almost all \(k\)-colorable graphs are easy to color ⋮ On the Laplacian Eigenvalues of G_n,p ⋮ On the tractability of coloring semirandom graphs ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ Diffusion representations ⋮ Recovering the structure of random linear graphs ⋮ Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks ⋮ Community detection in sparse networks via Grothendieck's inequality ⋮ Expansion and Lack Thereof in Randomly Perturbed Graphs ⋮ Group-Level Analysis and Visualization of Social Networks ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ The resolution complexity of random graph \(k\)-colorability ⋮ Ordered 3-colorings ⋮ Heuristics for semirandom graph problems ⋮ Finding Pseudorandom Colorings of Pseudorandom Graphs ⋮ Top eigenpair statistics for weighted sparse graphs

This page was built for publication: A Spectral Technique for Coloring Random 3-Colorable Graphs