随机图的Grundy数

作者：刘沈荣

来源：绵阳师范学院学报, 2009, (11): 22-24.

DOI：10.16276/j.cnki.cn51-1670/g.2009.11.007

• 首先适应着色数
• 随机图
• Grundy数 first-fit number
• random graph
• Grundy number

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

• 单位
  湖南商务职业技术学院