Tight bounds on the threshold for permuted k-colorability

Varsha Dani, Cristopher Moore, Anna Olson

If each edge (u,v) of a graph G=(V,E) is decorated with a permutation pi_{u,v} of k objects, we say that it has a permuted k-coloring if there is a coloring sigma from V to {1,...,…