Chromatic number, clique subdivisions, and the conjectures of Hajós and Erd?s-Fajtlowicz

详细信息    查看全文

• 作者：Jacob Fox (12853)
  Choongbum Lee (22853)
  Benny Sudakov (22853)
  
• 关键词：05D10 ; 05C55
• 刊名：Combinatorica
• 出版年：2013
• 出版时间：April 2013
• 年：2013
• 卷：33
• 期：2
• 页码：181-197
• 全文大小：224KB
• 参考文献：1. N. Alon : Explicit Ramsey graphs and orthonormal labelings, / Electron. J. Combin. g class="a-plus-plus">1g> (1994), R12.
  2. N. Alon, M. Krivelevich and B. Sudakov : Turan numbers of bipartite graphs and related Ramsey-type questions, / Combinatorics, Probability and Computing g class="a-plus-plus">12g> (2003), 477-94. g/10.1017/S0963548303005741">CrossRef
  3. B. Bollobás : The chromatic number of random graphs, / Combinatorica g class="a-plus-plus">8g> (1988), 49-5. g/10.1007/BF02122551">CrossRef
  4. B. Bollobás and P. A. Catlin : Topological cliques of random graphs, / J. Combin. Theory Ser. B g class="a-plus-plus">30g> (1981), 224-27. g/10.1016/0095-8956(81)90066-6">CrossRef
  5. B. Bollobás and A. Thomason : Proof of a conjecture of Mader, Erd?s and Hajnal on topological complete subgraphs, / European J. Combin. g class="a-plus-plus">19g> (1998), 883-87. g/10.1006/eujc.1997.0188">CrossRef
  6. P. Catlin : Hajós-graph-coloring conjecture: variations and counterexamples, / J. Combin. Theory Ser. B g class="a-plus-plus">26g> (1979), 268-74. g/10.1016/0095-8956(79)90062-5">CrossRef
  7. G. Dirac : A property of 4-chromatic graphs and some remarks on critical graphs, / J. London Math. Soc. 27 (1952), 85-2. g/10.1112/jlms/s1-27.1.85">CrossRef
  8. P. Erd?s and S. Fajtlowicz : On the conjecture of Hajós, / Combinatorica g class="a-plus-plus">1g> (1981), 141-43. g/10.1007/BF02579269">CrossRef
  9. P. Erd?s and E. Szemerédi : On a Ramsey type theorem, / Period. Math. Hungar. g class="a-plus-plus">2g> (1972), 295-99. g/10.1007/BF02018669">CrossRef
  10. J. Fox and B. Sudakov : Density theorems for bipartite graphs and related Ramsey-type results, / Combinatorica g class="a-plus-plus">29g> (2009), 153-96.
  11. J. Fox and B. Sudakov : Dependent random choice, / Random Structures Algorithms g class="a-plus-plus">38g> (2011), 1-2. g/10.1002/rsa.20344">CrossRef
  12. T. Gowers : A new proof of Szemerédi’s theorem for arithmetic progressions of length four, / Geom. Funct. Anal. g class="a-plus-plus">8g> (1998), 529-51. g/10.1007/s000390050065">CrossRef
  13. J. Komlós and E. Szemerédi : Topological cliques in graphs. II, / Combin. Probab. Comput. g class="a-plus-plus">5g> (1996), 79-0. g/10.1017/S096354830000184X">CrossRef
  14. A. V. Kostochka and V. R?dl : On graphs with small Ramsey numbers, / J. Graph Theory g class="a-plus-plus">37g> (2001), 198-04. g/10.1002/jgt.1014">CrossRef
  15. M. Krivelevich and B. Sudakov : Pseudo-random graphs, in: / More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies g class="a-plus-plus">15g>, Springer, 2006, 199-62.
  16. D. Kühn and D. Osthus : Topological minors in graphs of large girth, / J. Combin. Theory Ser. B g class="a-plus-plus">86g> (2002), 364-80. g/10.1006/jctb.2002.2133">CrossRef
  17. B. Sudakov : Few remarks on the Ramsey-Turán-type problems, / J. Combin Theory Ser. B g class="a-plus-plus">88g> (2003), 99-06. g/10.1016/S0095-8956(02)00038-2">CrossRef
  18. B. Sudakov : A conjecture of Erd?s on graph Ramsey numbers, / Adv. Math. g class="a-plus-plus">227g> (2011), 601-09. g/10.1016/j.aim.2011.02.004">CrossRef
  19. C. Thomassen : Some remarks on Hajós-conjecture, / J. Combin. Theory Ser. B g class="a-plus-plus">93g> (2005), 95-05. g/10.1016/j.jctb.2004.08.005">CrossRef
  
• 作者单位：Jacob Fox (12853)
  Choongbum Lee (22853)
  Benny Sudakov (22853)
  
  12853. Department of Mathematics, MIT, Cambridge, MA, 02139-4307, UK
  22853. Department of Mathematics, UCLA, Los Angeles, CA, 90095, USA
  

文摘

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ?χ(G) for every graph G. That is, H(n)? for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)?em class="a-plus-plus">cn 1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ?Cn 1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.