论文部分内容阅读
图G=(V,E)的首先适应着色数是在贪婪着色中最坏情形所需要的颜色数,记为xFF(G)。也称之为Grundy数,其等价定义为:V的有序拆分V1,V2,…,Vk的最大分类数为k,其中Vi为独立集且对每个1≤i〈j≤k及x∈Vj存在-y∈Vi使得x和y相连。文章证明了在稀疏随机图中,可以很高的概率满足(1-ε)n/logbnp≤xFF(G(n,P))≤(1+ε)n/logbnp。其中事件A以很高的概率成立是指对于任意当n→∞时,P(A发生)→1。