If each edge (u, v) of a graph G = (V, E) is decorated with a permutation πu,v of k objects, we say that it has a permuted k-coloring if there is a coloring σ : V → {1, . . . , k} such that σ(v) = πu,v(σ(u)) for all (u, v) ∈ E. Based on arguments from statistical physics, we conjecture that the threshold d k for permuted k-colorability in random graphs G(n, m = dn/2), where the permutations on the edges are uniformly random, is equal to the threshold for standard graph k-colorability. The additional symmetry provided by random permutations makes it easier to prove bounds on d k . By applying the second moment method with these additional symmetries, and applying the first moment method to a random variable that depends on the number of available colors at each vertex, we bound the threshold within an additive constant. Specifically, we show that for any constant ε > 0, for sufficiently large k we have In contrast, the best known bounds on d k for standard k-colorability leave an additive gap of about ln k between the upper and lower bounds.
Dani, Moore and Olson REF studied a "decorated" coloring problem in which each pair of (u, v) of vertices comes with a permutation π u,v of the k possible colors.
Tight bounds on the threshold for permuted k-colorability
ArXiv
ArXiv
Mathematics Physics Computer Science