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)

1164

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] GAO Wei, NI Guanqun. Cooperation strategy between retailers and community group buying platforms considering the time sensitive differences of consumers [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(9): 99-109.
[2] BAI Yu, QIANG Huiying, HE Jing. Neighbor sum distinguishing edge coloring of join graphs Cm∨Cn [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(12): 161-166.
[3] Lianjie ZHANG,Wei LI,Ping YANG,Min ZENG,Qiuwang WANG. Effect of PCM-PCHE on SCO2 Brayton cycle under variable operating conditions [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(11): 74-84.
[4] Jin LI,Changqing XU. Adjacent vertex distinguishing edge coloring of IC-planar graphs without intersecting triangles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 134-139.
[5] SUO Meng-ge, CHEN Jing-rong, ZHANG Juan-min. k-Path vertex cover in Cartesian product graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 103-110.
[6] MA Li-li, WU Di, LI Qiang, XU Jing. On Abelian extensions of Hom-δ-Jordan Lie triple systems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(10): 1-5.
[7] MA Li-li, DAI Di, LI Qiang. Constitutions and Abelian extensions of δ-Jordan Lie supertriple systems [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(8): 76-80.
[8] YANG Han, CHEN Xiang-en. Vertex-distinguishing Ⅰ-total colorings and vertex-distinguishing Ⅵ-total colorings of mC7 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(11): 76-82.
[9] TAN Xiang. Total colorings of one type of planar graphs with maximum degree 6 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(11): 71-75.
[10] LIU Zhuo-ya, XU Chang-qing. Adjacent vertex distinguishing edge coloring of planar graphs without intersecting triangles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(9): 36-41.
[11] MA Li-li, LI Qiang. Abelian extensions of δ-Lie color algebras [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(8): 38-42.
[12] CHEN Hong-yu, ZHONG Bin. Linear 2-arboricity of planar graphs without intersecting 5-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(7): 38-45.
[13] CHEN Chen, GAO Ying-ying, CHEN Hui-xiang. Lazy 2-cocycles on 9-dimensional Taft algebra [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(2): 73-78.
[14] 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.
[15] 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.
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