Problem 717

Let $G$ be a graph on $n$ vertices with chromatic number $\chi(G)$ and let $\sigma(G)$ be the maximal $k$ such that $G$ contains a subdivision of $K_k$ . Is it true that

\chi(G) \ll \frac{n^{1/2}}{\log n}\sigma(G)?

Source: erdosproblems.com/717

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The answer is yes: Theorem 1.1 (Fox 2013) of Fox, Lee and Sudakov [FLS13] (Combinatorica 33 (2013), 181--197, refereed; paged from arXiv v3 of 14 February 2012) gives an absolute constant $C$ with $H(n)\le Cn^{1/2}/\log n$ for $n\ge2$ , and the paper says $C=10^{120}$ suffices, without optimizing it. The order is exact: Theorem 3 (Erdős and Fajtlowicz 1981) of Erdős and Fajtlowicz [ErFa81] (Combinatorica 1 (1981), 141--143, refereed) gives $H(G)>C\sqrt n/\log n$ for almost all graphs on $n$ vertices, and [FLS13] (p. 2) records the sharper $H(n)\ge(\frac1{e\sqrt2}-o(1))n^{1/2}/\log n$ from the random graph at $p=1-e^{-2}$ . Acceptance evidence: publication in Combinatorica (per its Crossref record), the credit of the site's curator, Thomas Bloom, and the citing literature found by the search, which contains no dispute. The claim page Fox, Lee and Sudakov 2011 records the result, its scope and its acceptance evidence, from which the frontmatter standing is derived.

FLS13: Fox, Jacob and Lee, Choongbum and Sudakov, Benny, Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz. Combinatorica 33 (2013), no. 2, 181--197, doi:10.1007/s00493-013-2853-x (issued April 2013, online 14 June 2013, per the Crossref record; the site's reference text gives the journal, year and pages without the volume). Paged from arXiv:1107.1920v3 (14 February 2012, 14 pp., the latest arXiv version): Theorem 1.1 and Theorem 1.2, p. 2; the deduction, pp. 3--4; Theorem 3.1, p. 4. Library home: Fox 2013; paged at Fox 2013, Theorem 1.1, Fox 2013, Theorem 1.2 and Fox 2013, Theorem 3.1 (Bollobás–Thomason, Komlós–Szemerédi, as quoted).
ErFa81: Erdős, Paul and Fajtlowicz, Siemion, On the conjecture of Hajós. Combinatorica 1 (1981), no. 2, 141--143, doi:10.1007/BF02579269 (June 1981; received 8 June 1979). Theorems 1--3 and the Lemma, p. 142; the closing conjecture, p. 143. Library home: Erdős and Fajtlowicz 1981 (from the scan in the Erdős archive of the Rényi Institute); paged at Erdős and Fajtlowicz 1981, Theorem 3 (p. 142).
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), no. 1, 25--42, doi:10.1007/BF02579174 (March 1981); Part IV, item 2, p. 8 of the re-typeset copy in the Erdős archive of the Rényi Institute, which has its own pagination. Library home: Erdős 1981.
Ca74: Catlin, Paul A., Subgraphs of graphs. I. Discrete Math. 10 (1974), no. 2, 225--233, doi:10.1016/0012-365X(74)90119-8. Not held; cited for context (Catlin's counterexamples to Hajós's conjecture). [ErFa81] cites Catlin's later paper, Hajós' graph-coloring conjecture: variations and counterexamples, J. Combin. Theory Ser. B 26 (1979), 268--274, for the disproof, as does [FLS13] ("in 1979, Catlin [6] disproved the conjecture for all $\chi(G)\ge7$ "); the site's key is the 1974 paper, which Erdős's 1981 paper also cites for it.
Di52: Dirac, G. A., A property of $4$ -chromatic graphs and some remarks on critical graphs. J. London Math. Soc. 27 (1952), 85--92, doi:10.1112/jlms/s1-27.1.85. Not held; context, the case $\chi(G)\le4$ of Hajós's conjecture, quoted from the site and [FLS13].

Problem 717

Status

Proof claims

Discussion