JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2017, Vol. 52 ›› Issue (2): 37-38.doi: 10.6040/j.issn.1671-9352.0.2016.343

Previous Articles     Next Articles

Classification on f-coloring of graphs with some restrictions

YANG Chun-hua, CAI Jian-sheng   

  1. School of Mathematics and Information Sciences, Weifang University, Weifang 261061, Shandong, China
  • Received:2016-07-17 Online:2017-02-20 Published:2017-01-18

PDF (PC)

610

Abstract: A special class of f-coloring of graphs is investigated, and a sufficient condition is obtained for the special class of f-coloring of a simple graph being f-class 1 by the first moment principle.

Key words: coloring, maximum degree, the first moment principle, f-coloring

CLC Number: 

  • O157.5
[1] HAKIMI S L, KARIV O. A generalization of edge-coloring in graphs[J]. J Graph Theory, 1986, 10:139-154.
[2] BONDY J A, MURTY U S R. Graph Theory with applications[M]. New York: Macmillan Press, 1976.
[3] NAKANO S I, NISHIZEKI T, SAITO N. On the f-coloring of multigraphs[J]. IEEE Trans Circuit and Sys, 1988, 35(3):345-353.
[4] NAKANO S, NISHIZEKI T, SAITO N. On the fg-coloring of graphs[J]. Gombinatorica, 1990, 10(1):67-80.
[5] NAKANO S, NISHIZEKI T. An approximation algorithm for fg-edge-coloring Multigraphs[J]. Trans of Japan SIAM, 1991(1):195-211.
[6] HILTON A J W. Coloring the edges of a multigraph so that each vertex has at most j, or at least j edges of each color on it[J]. J London Math Soc, 1975, 12:123-128.
[7] MIAO Lianying. The classification of graphs on edge covering coloring[J]. J of Math, 2001, 21(4):369-372.
[8] ZHANG Xia, LIU Guizhen. The classification of complete graphs Kn on f-coloring[J]. J Applied Mathematics&Computing, 2005, 19(1-2):127-133.
[9] 张霞. 图的f-染色和均匀边染色[D]. 济南:山东大学, 2007. ZHANG Xia. The f-coloring and the equitable edge-coloring of graphs[D]. Jinan: Shandong University, 2007.
[10] BECK J. An Algorithmic Approach to the Lovász local lemma I[J]. Random Structures & Algorithms, 1991(2):343-365.
[11] ALON N, MCDIARMID C, REED B. Acyclic coloring of graphs[J]. Random Structures and Algotithms, 1991, 2:277-288.
[12] CZUMAJ A, SCHIEDELER C. Coloring nonuniform hypergraphs: a new algorithmic approach to the general Lovasz local lemma[J]. Random Structures & Algorithms, 2000, 17:213-237.
[13] BOLLOBAS B. The chromatic number of random graphs[J]. Combinatorica, 1988, 8:49-55.
[14] GREENHILL C, PIKHURKO O. Bounds on the generalized acyclic chromatic number of bounded degree graphs[J]. Graphs Combin, 2005, 21:407-419.
[15] ERDÖS P. Graph theory and probability[J]. Canadian J of Math, 1959, 11:34-38.
[16] MOLLOY M, REED B. Graph colouring and the probabilistic method[M] // Algorithms and Combinatorics. New Yorks: Springer, 2002: 27-37.
[1] . Vertex-distinguishing IE-total coloring and general-total coloring of K1,3,p and K1,4,p [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 53-60.
[2] FANG Qi-ming, ZHANG Li. k-frugal list coloring of planar graphs without 4 and 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 35-41.
[3] WANG Xiao-li, WANG Hui-juan, LIU Bin. Total coloring of planar graphs with maximum degree seven [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 100-106.
[4] PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing index of a kind of sparse graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 94-99.
[5] CHEN Xiang-en, MIAO Ting-ting, WANG Zhi-wen. Vertex-distinguishing I-total colorings of the join of two paths [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 30-33.
[6] HE Yu-ping, WANG Zhi-wen, CHEN Xiang-en. Vertex-distinguishing total coloring of mC8 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(10): 24-30.
[7] LI Shi-ling, CHEN Xiang-en, WANG Zhi-wen. Vertex-Distinguishing E-Total coloring of complete bipartite graph K3,n with n≥18 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 68-71.
[8] TAN Xiang. Total colorings of planar graphs without 6-cycles and adjacent 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 72-78.
[9] SONG Hong-jie, GONG Xiang-nan, PAN Wen-hua, XU Chang-qing. Neighbor sum distinguishing total coloring of Halin graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 65-67.
[10] ZHU Hai-yang, GU Yu, LÜ Xin-zhong. New upper bound on the chromatic number of the square of a planar graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(2): 94-101.
[11] MENG Xian-yong, GUO Jian-hua, SU Ben-tang. The complete coloring of 3-regular Halin graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(12): 127-129.
[12] MENG Xian-qing. Strong edge coloring of a class of planar graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(08): 10-13.
[13] HE Xue, TIAN Shuang-liang. Adjacent vertex-distinguishing edge/total colorings of double graph of some graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(04): 63-66.
[14] LI Jing-wen, JIA Xi-bei, DONG Wei, LI Xiao-hui, YAN Guang-hui. The algorithm for adjacent-vertex-distinguishing total coloring of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 14-21.
[15] YAO Jing-jing, XU Chang-qing. Neighbor sum distinguishing total coloring of graphs with maximum degree 3 or 4 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 9-13.
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