Coloring complete bipartite graphs from random lists

Abstract: Let

K_{n, n}

be the complete bipartite graph with

n

vertices in each side. For each vertex draw uniformly at random a list of size

k

from a base set

S

of size

s = s (n)

. In this paper we estimate the asymptotic probability of the existence of a proper colouring from the random lists for all fixed values of

k

and growing

n

. We show that this property exhibits a sharp threshold for

k g e q 2

and the location of the threshold is precisely

s (n) = 2 n

for

k = 2

, and approximately

s (n) = f r a c n 2^{k - 1} l n 2

for

k g e q 3

.

Recommendations

Cites work

Cited in

(26)

This page was built for publication: Coloring complete bipartite graphs from random lists