论文部分内容阅读
图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。