On the span of a random channel assignment problem (Q2460622)

The chromatic number of a random graph \(G(n,p)\) with fixed edge probability \(p\) is generalized to the span of a random graph with fixed probabilities \(p_2\), \(p_1\), \(p_0\) of long, short, and missing edges. The span is defined as the minimum number of integer color labels needed for vertex coloring when it is required that vertices with long and short edges should have color labels that are at least two or one units apart, respectively. The asymptotic behaviour of the span is determined and a phase change is identified at the curve \(p_1=p_2(1-p_2)\).