JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2019, Vol. 54 ›› Issue (6): 71-74.doi: 10.6040/j.issn.1671-9352.0.2018.333

Previous Articles    

The classification of f-coloring of random graphs

XIONG Ya-ping1, CAI Jian-sheng2*   

  1. 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: 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

CLC Number: 

  • O157.5
[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 cf 1[J]. Applied Mathematics Letters, 2006, 19(1):38-44.
[4] ZHANG Xia, LIU Guizhen. The classication of complete graphs Kn 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.
[1] ZHANG Wei-wei, CAI Jian-sheng. K4-factors in random graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(4): 86-90.
[2] YANG Chun-hua, CAI Jian-sheng. Classification on f-coloring of graphs with some restrictions [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(2): 37-38.
[3] LIU Xin-sheng, WEI Zi-ying. An upper bound for the adjacent vertex-distinguishing star chromatic number of graphs [J]. J4, 2012, 47(2): 52-55.
[4] QIANG Hui-ying. A bound of the vertex-distinguishing total chromatic number of graphs [J]. J4, 2011, 46(6): 53-56.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd