随机图的f-染色的分类Ⅱ

摘要

随机图G(n,p)是具有n个标号的顶点的图,并且图中的每一对顶点以概率p被随机且独立地选择为图G的边.对于有顶点集V和边集E的简单图G=(V,E),G的f-染色c是广义的边染色,使每个颜色类在任一顶点v上至多出现f(v)次,其中f(v)是分配给v的正整数.在这篇文章中,我们给出随机图G(n,p)是f-第一类的一个充分条件.