JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2018, Vol. 53 ›› Issue (10): 35-41.doi: 10.6040/j.issn.1671-9352.0.2017.648

Previous Articles     Next Articles

k-frugal list coloring of planar graphs without 4 and 5-cycles

FANG Qi-ming, ZHANG Li*   

  1. School of Mathematical Sciences, Tongji University, Shanghai 200092, China
  • Received:2017-12-15 Online:2018-10-20 Published:2018-10-09

Abstract: For a graph G, c is a proper vertex coloring of G. If every color appears at most k-1 times in the neighbors of each vertex v, then c is called a k-frugal coloring of G. There are two conclusions on the k-frugal list coloring of planar graphs without 4 and 5-cycles:(1)For each planar graph without 4 and 5-cycles, if its maximum degree is Δ and Δ≥3k+8, then the k-frugal list chromatic number is less than or equal to 「(Δ)/(k-1)+2; (2)For each planar graph without 4 and 5-cycles, its k-frugal list chromatic number is no more than 「(Δ)/(k-1)+5.

Key words: frugal list coloring, planar graph, cycle

CLC Number: 

  • O158
[1] BONDY J, MURTY U. Graph theory[M]. London: Springer, 2008.
[2] HIND H, MOLLOY M, REED B. Colouring a graph frugally[J]. Combinatorica, 1997, 17(4):469-482.
[3] YUSTER R. Linear coloring of graphs[J]. Discrete Mathematics, 1998, 185(1-3):293-297.
[4] ESPERET L, MONTASSIER M, RASPAUD A. Linear choosability of graphs[J]. Discrete Mathematics, 2015, 308(17):3938-3950.
[5] CRANSTON D, YU G. Linear choosability of sparse graphs[J]. Discrete Mathematics, 2010, 311(17):1910-1917.
[6] BORODIN O, FONDER F D, KOSTOCHKA A, et al. Acyclic list 7-coloring of planar graphs[J]. Journal of Graph Theory, 2002, 40(2):83-90.
[7] COHEN N. Linear and 2-frugal choosability of graphs of small maximum average degree[J]. Graphs & Combinatorics, 2011, 27(6):831-849.
[8] ERD″/OS P, RUBIN A, TAYLOR H. Choosability in graphs[C] // West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium, 1979, 26:125-157.
[9] RASPAUD A, WANG W. Linear coloring of planar graphs with large girth[J]. Discrete Mathematics, 2009, 309(18):5678-5686.
[10] AMINI O, ESPERET L, HEUVEL J. Frugal colouring of graphs[J/OL]. arXiv: 0705.0422, 2007. http://cn.arxiv.org/abs/0705.0422.
[11] STEINBERG R. The state of the three color problem[J]. Annals of Discrete Mathematics, 1993, 55(08):211-248.
[12] WANG Deqiang, WEN Yupeng, WANG Kelun. A smaller planar graph without 4-, 5-cycles and intersecting triangles that is not 3-choosable[J]. Information Processing Letters, 2008, 108(3):87-89.
[13] VOIGT M. A non-3-choosable planar graph without cycles of length 4 and 5[J]. Discrete Mathematics, 2007, 307(7):1013-1015.
[1] 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.
[2] WANG Ye, SUN Lei. Every 1-planar graph without cycles of length 3 or 4 is 5-colorable [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 34-39.
[3] CHEN Hong-yu, ZHANG Li. Linear 2-arboricity of planar graphs with 4-cycles have no common vertex [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(12): 36-41.
[4] 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.
[5] YU Xiao-lan. Global dimensions of cocycle deformations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 39-43.
[6] 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.
[7] BAI Dan, ZUO Lian-cui. The(d,1)-total labelling of the cube of cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(4): 59-64.
[8] WANG Jia-jiang, CHEN Ling, MEN Yu-tao, JI Chen. The feasibility study on shorten treatment cycle of dental implantation and split-root technique joint repair [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(3): 40-43.
[9] 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.
[10] WU Zi-juan, CHEN Yuan-yuan, ZHANG Liang-yun. Quasidimodule algebras over Hopf quasigroups and Yetter-Drinfeld quasimodule algebras [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(10): 28-33.
[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] XUE Li-xia, LI Zhi-hui, XIE Jia-li. A note on the optimal information rate of hypercycle access structure with three hyperedges [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(11): 60-66.
[13] WANG Shan-shan, QI En-feng. On the number of contractible edges of longest cycles in k-connected graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(10): 27-31.
[14] MENG Xian-qing. Strong edge coloring of a class of planar graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(08): 10-13.
[15] ZHANG Shao-hua, YAN Jin, LI Shuo. Disjoint 4-cycles and 8-cycles in graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(02): 1-4.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!