(1,0,0)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1,0,0)$$\end{document}-Colorability of planar graphs without prescribed short cycles

被引:0
作者
Yuehua Bu
Jinghan Xu
Yingqian Wang
机构
[1] Zhejiang Normal University,College of Mathematics, Physics and Information Engineering
关键词
Planar graph; Steinberg conjecture; Improper coloring; Cycle;
D O I
10.1007/s10878-013-9653-5
中图分类号
学科分类号
摘要
Let d1,d2,…,dk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d_1, d_2,\ldots ,d_k$$\end{document} be k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document} non-negative integers. A graph G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} is (d1,d2,…,dk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(d_1,d_2,\ldots ,d_k)$$\end{document}-colorable, if the vertex set of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} can be partitioned into subsets V1,V2,…,Vk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V_1,V_2,\ldots ,V_k$$\end{document} such that the subgraph G[Vi]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G[V_i]$$\end{document} induced by Vi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V_i$$\end{document} has maximum degree at most di\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d_i$$\end{document} for i=1,2,…,k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i=1,2,\ldots ,k$$\end{document}. Let ϝ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\digamma $$\end{document} be the family of planar graphs with cycles of length neither 4 nor 8. In this paper, we prove that a planar graph in ϝ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\digamma $$\end{document} is (1,0,0)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1,0,0)$$\end{document}-colorable if it has no cycle of length k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document} for some k∈{7,9}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\in \{7,9\}$$\end{document}. Together with other known related results, this completes a neat conclusion on the (1,0,0)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1,0,0)$$\end{document}-colorability of planar graphs without prescribed short cycles, more precisely, for every triple (4,i,j)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(4,i,j)$$\end{document}, planar graphs without cycles of length 4, i\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$i$$\end{document} or j\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j$$\end{document} are (1,0,0)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1,0,0)$$\end{document}-colorable whenever 4<i<j≤9\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$4<i<j\le 9$$\end{document}.
引用
收藏
页码:627 / 646
页数:19
相关论文
共 41 条
  • [1] Borodin OV(2005)Planar graphs without cycles of length from 4 to 7 are 3-colorable J Comb Theory B 93 303-311
  • [2] Glebov AN(2009)Planar graphs without 5- and 7-cycles without adjacent triangles are 3-colorable J Comb Theory B 99 668-673
  • [3] Raspaud A(2010)Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable Discret Math 310 2584-2594
  • [4] Salavatipour MR(1986)Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency J Graph Theory 10 187-195
  • [5] Borodin OV(1959)Ein dreifarbensatz für dreikreisfreie netze auf der kugel Math -nat Reihe 8 109-120
  • [6] Glebov AN(2013)Planar graphs without 4-cycles or 5-cycles are $$(3,0,0)$$ ( 3 , 0 , 0 ) -colorable Discret Math 313 2312-2317
  • [7] Montassier M(2009)On the 3-colorability of planar graphs without 4-, 7- and 9-cycles Discret Math 309 4596-4607
  • [8] Raspaud A(2011)Planar graphs without 4-, 5- and 8-cycles are 3-colorable Discuss Math 31 P775-1562
  • [9] Borodin OV(2007)Planar graphs without 4, 6, 8-cycles are 3-colorable Sci China A 50 1552-158
  • [10] Glebov AN(2010)Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable Discret Math 310 147-239