随机图的f-染色的分类

doi:10.6040/j.issn.1671-9352.0.2018.333

《山东大学学报(理学版)》 ›› 2019, Vol. 54 ›› Issue (6): 71-74.doi: 10.6040/j.issn.1671-9352.0.2018.333

• • 上一篇

随机图的f-染色的分类

熊亚萍¹, 蔡建生^2*

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

发布日期:2019-06-05
作者简介:熊亚萍(1994— ), 女, 硕士研究生, 研究方向为图论. E-mail:2671993698@qq.com *通信作者简介:蔡建生(1966— ), 男, 博士, 教授, 硕士生导师, 研究方向为组合数学与图论. E-mail:jscai@wfu.edu.cn
基金资助:
国家自然科学基金资助项目(11571258)

The classification of f-coloring of random graphs

XIONG Ya-ping¹, CAI Jian-sheng^2*

1. School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, Shandong, China;
2. School of Mathematics and Information Science, Weifang University, Weifang 261061, Shandong, China

Published:2019-06-05

摘要/Abstract

摘要： 随机图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-第一类的一个充分条件。

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

Abstract: A random graph G(n,p) is a graph on n labeled vertices, in which every pair of vertices is chosen to be an edge of G randomly and independently with probability p. In particular, when p=1/2, a probability space is given where all labeled graphs on n vertices are equiprobable. For a simple graph G=(V,E) with vertex set V and edge set E, an f-coloring c of G is a generalized edge-coloring in which each color class appears at each vertex v at most f(v) times where f(v) is a positive integer assigned to v. A sufficient condition for the random graph G(n,1/2) to be f-class 1 is given.

Key words: random graphs, f-coloring, local lemma

中图分类号:

O157.5

熊亚萍, 蔡建生. 随机图的f-染色的分类[J]. 《山东大学学报(理学版)》, 2019, 54(6): 71-74.

XIONG Ya-ping, CAI Jian-sheng. The classification of f-coloring of random graphs[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(6): 71-74.

参考文献

[1] VIZING V G. On an estimate of the chromatic class of a p-graph[J]. Metody Diskret Analiz, 1964, 3:25-30.
[2] HAKIMI S L, KARIV O. A generalization of edge-coloring of graphs[J]. Journal of Graph Theory, 1986, 10:139-154.
[3] ZHANG Xia, LIU Guizhen. Some sucient conditions for a graph to be c_f 1[J]. Applied Mathematics Letters, 2006, 19(1):38-44.
[4] ZHANG Xia, LIU Guizhen. The classication of complete graphs K_n on f-coloring[J]. Applied Mathematics and Computation, 2005, 19(1/2):127-133.
[5] 杨春花,蔡建生.限定条件下图的f-染色的分类[J]. 山东大学学报(理学版), 2017, 52(2):37-38, 43. YANG Chunhua, CAI Jiansheng. Classication on f-coloring of graphs with some restrictions[J]. Journal of Shandong University(Natural Science), 2017, 52(2):37-38, 43.
[6] 韩丽花. 图的f-染色的若干结果[D]. 曲阜:曲阜师范大学, 2007. HAN Lihua. Some results of f-coloring of graphs[D]. Qufu: Qufu Normal University, 2007.
[7] CAI Jiansheng, YAN Guiying, ZHANG Xia. The classication of f-coloring of graphs with large maximum degree[J]. Applied Mathematics and Computation, 2017, 313:119-121.
[8] MOLLOY M, REED B. Graph coloring and the probablistic method[M]. Berlin: Springer, 2002.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

随机图的f-染色的分类

The classification of f-coloring of random graphs

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

多维度评价

本文评价

推荐阅读 0

[1]	张伟伟,蔡建生. 随机图中的K₄-因子[J]. 《山东大学学报(理学版)》, 2019, 54(4): 86-90.
[2]	杨春花,蔡建生. 限定条件下图的f-染色的分类[J]. 山东大学学报（理学版）, 2017, 52(2): 37-38.
[3]	刘信生,魏自盈. 图的邻点可区别星边色数的一个上界[J]. J4, 2012, 47(2): 52-55.
[4]	强会英. 点可区别全色数的一个界[J]. J4, 2011, 46(6): 53-56.