JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2018, Vol. 53 ›› Issue (12): 31-40.doi: 10.6040/j.issn.1671-9352.0.2017.642

Previous Articles     Next Articles

Planar graphs without 4-cycle or chordal-6-cycle are(3,0,0)-colorable

LIU Jia, SUN Lei*   

  1. School of Mathematics and statistics, Shandong Normal University, Jinan 250014, Shandong, China
  • Online:2018-12-20 Published:2018-12-18

PDF (PC)

754

Abstract: Let d1,d2,…,dk be k non-negative intergers. A graph G is(d1,d2,…,dk)-colorable, if the vertex set of G can be partitioned into subsets V1,V2,…,Vk such that the graph G［Vi］ induced by Vi has maximum degree at most di for i=1,2,…,k. There is a conclusion about the coloring of planar graphs: planar graphs without 4-cycle or chordal-6-cycle are(3,0,0)-colorable.

Key words: planar graph, improper coloring, cycle, chordal-6-cycle

CLC Number: 

  • O157.5
[1] APPEL K. Every planar map is four colorable. Part I: Discharging[J]. Illinois Journal of Mathematics, 1977, 21:203-214.
[2] APPEL K, HAKEN W. Every planar map is four colorable. Part Ⅱ: Reducibility[J]. Illinois Journal of Mathematics, 1977, 21:491-567.
[3] GRÖTZSCH H. Zur theorie der diskreten gebilde, vii: ein dreifarbensatz für dreikreisfreie netze auf der kugel[J]. Wiss. Zeitschrift der Martin-Luther-Univ. Halle-Wittenberg, Math.-Nat, 1959, 8:109-120.
[4] COWEN L J, COWEN R H, WOODALL D R. Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valence[J]. Journal of Graph Theory, 1986, 10(2):187-195.
[5] XU B. On(3, 1)*-coloring of plane graphs[J]. Society for Industrial and Applied Mathematics, 2008, 23(1):205-220.
[6] STEINBERG R. The state of the three color problem[J]. Annals of Discrete Mathematics, 1993, 55(8):211-248.
[7] DONG W, XU B. A note on list improper coloring of plane graphs[J]. Discrete Appl Math, 2009, 157:433-436.
[8] CHANG G, HAVET F, MONTASSIER M, et al. Steinbergs conjecture and near-colorings[J]. Chemistry International-Newsmagazine for IUPAC, 2011, 26(2):4-7.
[9] HILL O, SMITH D, WANG Y Q, et al. Planar graphs without cycles of length 4 or 5 are(3,0,0)-colorable[J]. Discrete Mathematics, 2013, 313(20):2312-2317.
[10] HILL O, YU G. A relaxation of Steinbergs conjecture[J/OL]. SIAM J Discrete Math, 27(1):584-596. arXiv:1208.3395v1.http://arxiv.org/abs/1208.3395v1.
[11] XU L, MIAO Z, WANG Y. Every planar graph with cycles of length neither 4 nor 5 is(1,1,0)-colorable[M]. New York: Springer-Verlag, 2014.
[12] 徐灵姬, 王应前. 既不含4-圈又不含6-圈的平面图的非正常染色[J]. 中国科学:数学, 2013, 43(1):15-24. XU Lingji,WANG Yingqian. Improper colorability of planar graphs with cycles of length neither 4 nor 6[J]. Sci Sin Math, 2013, 43:15-24.
[13] LI H, XU J, WANG Y. Planar graphs with cycles of length neither 4 nor 7 are(3,0,0)[J]. Discrete Mathematics, 2014, 327:29-35.
[1] LI Qiang, MA Li-li, WANG Xiao-yan, LYU Li-jiao. Abelian extensions of Hom-Jordan Lie algebras [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 4-8.
[2] CHEN Hong-ling, WANG Hui-juan, GAO Hong-wei. Linear arboricity of graphs embedded in a surface of non-negative Euler characteristic [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 17-22.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] YU Xiao-lan. Global dimensions of cocycle deformations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2016, 51(8): 39-43.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] YANG Jun. Characterization and structural control of metalbased nanomaterials[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 1 -22 .
[2] HE Hai-lun， CHEN Xiu-lan* . Circular dichroism detection of the effects of denaturants and buffers on the conformation of cold-adapted protease MCP-01 and  mesophilic protease BP01[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 23 -29 .
[3] ZHAO Jun1, ZHAO Jing2, FAN Ting-jun1*, YUAN Wen-peng1,3, ZHANG Zheng1, CONG Ri-shan1. Purification and anti-tumor activity examination of water-soluble asterosaponin from Asterias rollestoni Bell[J]. J4, 2013, 48(1): 30 -35 .
[4] SUN Xiao-ting1, JIN Lan2*. Application of DOSY in oligosaccharide mixture analysis[J]. J4, 2013, 48(1): 43 -45 .
[5] LUO Si-te, LU Li-qian, CUI Ruo-fei, ZHOU Wei-wei, LI Zeng-yong*. Monte-Carlo simulation of photons transmission at alcohol wavelength in  skin tissue and design of fiber optic probe[J]. J4, 2013, 48(1): 46 -50 .
[6] YANG Lun, XU Zheng-gang, WANG Hui*, CHEN Qi-mei, CHEN Wei, HU Yan-xia, SHI Yuan, ZHU Hong-lei, ZENG Yong-qing*. Silence of PID1 gene expression using RNA interference in C2C12 cell line[J]. J4, 2013, 48(1): 36 -42 .
[7] MAO Ai-qin1,2, YANG Ming-jun2, 3, YU Hai-yun2, ZHANG Pin1, PAN Ren-ming1*. Study on thermal decomposition mechanism of  pentafluoroethane fire extinguishing agent[J]. J4, 2013, 48(1): 51 -55 .
[8] YANG Ying, JIANG Long*, SUO Xin-li. Choquet integral representation of premium functional and related properties on capacity space[J]. J4, 2013, 48(1): 78 -82 .
[9] LI Yong-ming1, DING Li-wang2. The r-th moment consistency of estimators for a semi-parametric regression model for positively associated errors[J]. J4, 2013, 48(1): 83 -88 .
[10] YANG Yong-wei1, 2, HE Peng-fei2, LI Yi-jun2,3. On strict filters of BL-algebras#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 63 -67 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd