On a Coloring Conjecture of Hajós

详细信息    查看全文

• 作者：Yuqin Sun ; Xingxing Yu
• 关键词：Coloring ; Subdivision of graph ; Independent paths ; Planar graph ; 05C15 ; 05C38 ; 05C40 ; 05C75
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：32
• 期：1
• 页码：351-361
• 全文大小：454 KB
• 参考文献：1.Catlin, P.: Hajós’ graph-coloring conjecture: variations and counterexamples. J. Comb. Theory Ser. B 26, 268–274 (1979)MATH MathSciNet CrossRef
  2.Dirac, G.A.: A property of 4-chromatic graphs and some remarks on critical graphs. J. Lond. Math. Soc. Ser. B 27, 85–92 (1952)MATH MathSciNet CrossRef
  3.Erdös, P., Fajtlowicz, S.: On the conjecture of Hajós. Combinatorica 1, 141–143 (1981)MATH MathSciNet CrossRef
  4.Kelmans, A.K.: Every minimal counterexample to the Dirac conjecture is 5-connected. Lectures to the Moscow Seminar on Discrete Mathematics, (1979)
  5.Ma, J., Yu, X.: Independent paths and \(K_5\) -subdivisions. J. Comb. Theory Ser. B 100, 600–616 (2010)MATH MathSciNet CrossRef
  6.Ma, J., Yu, X.: \(K_5\) -Subdivisions in graphs containing \(K_4^-\) . J. Comb. Theory Ser. B 103, 713–732 (2013)MathSciNet CrossRef
  7.Mader, W.: \(3n-5\) Edges do force a subdivision of \(K_5\) . Combinatorica 18, 569–595 (1998)MATH MathSciNet CrossRef
  8.Perfect, H.: Applications of Menger’s graph theorem. J. Math. Anal. Appl. 22, 96–111 (1968)MATH MathSciNet CrossRef
  9.Robertson, N., Chakravarti, K.: Covering three edges with a bond in a nonseparable graph. In: Deza, M., Rosenberg, G. (eds.) Combinatorics 79 Part I. Annals of discrete mathematics, p. 247 (1980)
  10.Seymour, P.D.: Private communication
  11.Seymour, P.D.: Disjoint paths in graphs. Discret. Math. 29, 293–309 (1980)MATH MathSciNet CrossRef
  12.Shiloach, Y.: A polynomial solution to the undirected two paths problem. J. Assoc. Comp. Mach. 27, 445–456 (1980)MATH MathSciNet CrossRef
  13.Thomassen, C.: 2-Linked graphs. Eur. J. Comb. 1, 371–378 (1980)MATH MathSciNet CrossRef
  14.Watkins, M.E., Mesner, D.M.: Cycles and connectivity in graphs. Can. J. Math. 19, 1319–1328 (1967)MATH MathSciNet CrossRef
  15.Yu, X., Zickfeld, F.: Reducing Hajos’ coloring conjecture to 4-connected graphs. J. Comb. Theory Ser. B 96, 482–492 (2006)MATH MathSciNet CrossRef
  
• 作者单位：Yuqin Sun (1)
  Xingxing Yu (2)
  
  1. School of Mathematics and Physics, Shanghai University of Electric Power, Shanghai, 200090, China
  2. School of Mathematics, Georgia Institute of Technology, Atlanta, GA, 30332-0160, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

Hajós conjectured that graphs containing no subdivision of \(K_5\) are 4-colorable. It is shown in Yu and Zickfeld (J Comb Theory Ser B 96:482–492, 2006) that if there is a counterexample to this conjecture then any minimum such counterexample must be 4-connected. In this paper, we further show that if \(G\) is a minimum counterexample to Hajós’ conjecture and \(S\) is a 4-cut in \(G\) then \(G-S\) has exactly two components. Keywords Coloring Subdivision of graph Independent paths Planar graph