Dani, Varsha
[VerfasserIn];
Gupta, Diksha
[VerfasserIn];
Hayes, Thomas P.
[VerfasserIn]
;
Varsha Dani and Diksha Gupta and Thomas P. Hayes
[MitwirkendeR]
On the Power of Choice for k-Colorability of Random Graphs
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
In an r-choice Achlioptas process, random edges are generated r at a time, and an online strategy is used to select one of them for inclusion in a graph. We investigate the problem of whether such a selection strategy can shift the k-colorability transition; that is, the number of edges at which the graph goes from being k-colorable to non-k-colorable. We show that, for k ≥ 9, two choices suffice to delay the k-colorability threshold, and that for every k ≥ 2, six choices suffice.