\((1,0,0)\) -Colorability of planar graphs without prescribed short cycles

详细信息    查看全文

• 作者：Yuehua Bu ; Jinghan Xu ; Yingqian Wang
• 关键词：Planar graph ; Steinberg conjecture ; Improper coloring ; Cycle
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：30
• 期：3
• 页码：627-646
• 全文大小：717 KB
• 参考文献：Borodin OV, Glebov AN, Raspaud A, Salavatipour MR (2005) Planar graphs without cycles of length from 4 to 7 are 3-colorable. J Comb Theory B 93:303鈥?11MathSciNet CrossRef MATH
  Borodin OV, Glebov AN, Montassier M, Raspaud A (2009) Planar graphs without 5- and 7-cycles without adjacent triangles are 3-colorable. J Comb Theory B 99:668鈥?73MathSciNet CrossRef MATH
  Borodin OV, Glebov AN, Raspaud A (2010) Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable. Discret Math 310:2584鈥?594
  Chang GJ, Havet F, Montassier M, Raspaud A (preprint) Steinberg鈥檚 Conjecture and nearing-colorings
  Cowen LJ, Cowen RH, Woodall DR (1986) Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. J Graph Theory 10(2):187鈥?95MathSciNet CrossRef MATH
  Gr枚tzsch H (1959) Ein dreifarbensatz f眉r dreikreisfreie netze auf der kugel. Math -nat Reihe 8:109鈥?20
  Hill O, Smith D, Wang Y, Xu L, Yu G (2013) Planar graphs without 4-cycles or 5-cycles are \((3,0,0)\) -colorable. Discret Math 313:2312鈥?317
  Hill O, Yu G (2013) A relaxation of Steinberg鈥檚 conjecture, on arXiv. http://鈥媋rxiv.鈥媜rg/鈥媋bs/鈥?208.鈥?395
  Kang Y, Jin L, Wang Y (submitted) Planar graphs without cycles of length 4, 6, or 9 are 3-colorable
  Lu H, Wang Y, Wang W, Bu Y, Montassier M, Raspaud A (2009) On the 3-colorability of planar graphs without 4-, 7- and 9-cycles. Discret Math 309:4596鈥?607MathSciNet CrossRef MATH
  Mondal SA (2011) Planar graphs without 4-, 5- and 8-cycles are 3-colorable. Discuss Math 31(4):P775MathSciNet CrossRef
  Steinberg R (1993) The state of the three color problem. In: Gimbel J, Kenndy JW, Quintas LV (eds) Quo Vadis, Graph theory? Ann Diseret Math 55:211鈥?48
  Wang W, Chen M (2007) Planar graphs without 4, 6, 8-cycles are 3-colorable. Sci China A 50:1552鈥?562CrossRef MATH
  Wang Y, Lu H, Chen M (2010) Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable. Discret Math 310:147鈥?58MathSciNet CrossRef MATH
  Wang Y, Wu Q, Shen L (2011) Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable. Discret Appl Math 159:232鈥?39MathSciNet CrossRef MATH
  Wang Y, Jin L, Kang Y (in press) Planar graphs without cycles of length from 4 to 6 are (1,0,0)-colorable. Sci Chin Math (in Chinese)
  Wang Y, Yang Y (submitted-a) Planar graphs without cycles of length 4, 5 or 9 are (1,0,0)-colorable
  Wang Y, Yang Y (submitted-b) Planar graphs with cycles of length neither 4 nor 8 are (3,0,0)-colorable
  Wang Y, Xu J (2013) Planar graphs with cycles of length neither 4 nor 6 are (2,0,0)-colorable. Inform Process Lett 113:659鈥?63
  Wang Y, Xu J (submitted) Improper colorability of planar graphs without 4-cycles
  Wang Y, Xu J (manuscript) Planar graphs with cycles of length neither 4 nor 9 are (3,0,0)- and (1,1,0)-colorable
  Xu L, Miao Z, Wang Y (2013) Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\) -colorable. J Comb Optim. doi:10.鈥?007/鈥媠10878-012-9586-4
  Xu L, Wang Y (2013) Improper colorability of planar graphs with cycles of length neither 4 nor 6 (in Chinese). Sci Sin Math 43:15鈥?4CrossRef
  Xu B (2006) On 3-colorable plane graphs without 5- and 7-cycles. J Comb Theory B 96:958鈥?63CrossRef MATH
  Xu B (2009) On (3; 1)-coloring of plane graphs. SIAM J Discret Math 23(1):205鈥?20CrossRef
  Xu J, Li H, Wang Y (submitted) Planar graphs with cycles of length neither 4 nor 7 are (3,0,0)-colorable
  
• 作者单位：Yuehua Bu (1)
  Jinghan Xu (1)
  Yingqian Wang (1)
  
  1. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua, 321004, China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

Let \(d_1, d_2,\ldots ,d_k\) be \(k\) non-negative integers. A graph \(G\) is \((d_1,d_2,\ldots ,d_k)\)-colorable, if the vertex set of \(G\) can be partitioned into subsets \(V_1,V_2,\ldots ,V_k\) such that the subgraph \(G[V_i]\) induced by \(V_i\) has maximum degree at most \(d_i\) for \(i=1,2,\ldots ,k\). Let \(\digamma \) be the family of planar graphs with cycles of length neither 4 nor 8. In this paper, we prove that a planar graph in \(\digamma \) is \((1,0,0)\)-colorable if it has no cycle of length \(k\) for some \(k\in \{7,9\}\). Together with other known related results, this completes a neat conclusion on the \((1,0,0)\)-colorability of planar graphs without prescribed short cycles, more precisely, for every triple \((4,i,j)\), planar graphs without cycles of length 4, \(i\) or \(j\) are \((1,0,0)\)-colorable whenever \(4<i<j\le 9\). Keywords Planar graph Steinberg conjecture Improper coloring Cycle