随机图的f-染色的分类

随机图G(n,p)是具有n个标号的顶点的图,并且图中的每一顶点对都以概率p被随机且独立地选择为图G的边。特别地,当■时,得到一个概率空间,其中n个顶点上的所有标号图是等概率的。对于有顶点集V和边集E的简单图G=(V,E),G的f-染色c是广义的边染色,使每个颜色类在任一顶点v上至多出现f(v)次,其中f(v)是分配给v的正整数。给出随机图■是f-第一类的一个充分条件。