山东大学学报(理学版)

作者：熊亚萍, 蔡建生

单位：1.山东师范大学数学与统计学院, 山东 济南 250358;2.潍坊学院数学与信息科学学院, 山东 潍坊 261061

关键词：随机图,f-染色,局部引理,

基金：国家自然科学基金资助项目(11571258)

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

来源：2019年第6期

《山东大学学报(理学版)》期刊编辑部

查看山东大学学报(理学版)杂志2019年第6期