Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let . Is it true that, if is sufficiently large, then
for every graph with chromatic number ?
Even stronger, is there some such that, for all large , for every graph with chromatic number ?
Let . Is it true that, if is sufficiently large, then
for every graph with chromatic number ?
Even stronger, is there some such that, for all large , for every graph with chromatic number ?
Source: erdosproblems.com/87
No claim settles this problem.
Open, the site's label (OPEN). Both questions of the corrected Statement have no source in either direction. Erdős proposed them in 1995 after the unweakened conjecture had been refuted at by Faudree and McKay's computer-search value (J. Combin. Math. Combin. Comput. 13 (1993); Erdős's 1995 paper confirms the refutation), and Erdős wrote that "Both conjectures may be unattackable at present". The lower bounds in hand for with are exponential in but far below the known upper bounds for : Chvátal and Harary's as quoted by Erdős in 1981, and the site's remark, attributed to Wigderson, that by a random coloring, which is within a factor of order of the best known lower bound for . No source proving or refuting either weakening was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.
The site's "Let " admits every positive , and for the first question fails trivially: for even the factor is at least , and has and , so the inequality fails for every even . The smallest instance is , where for every even . The check is elementary and was made here; the formal-conjectures statement already restricts to , its docstring noting that the restriction excludes negative bases.
The change replaces "Let " by "Let "; nothing else changes. The evidence is the poser's own words. Erdős [Er95], Section II.15, p. 14 of the typescript (its card), writes that " should hold for some ", so Erdős's lies in . The site's commentary agrees: its remark "Since this is trivial for " rests on , which holds for every only when , so the remark is true only when is bounded and does not contemplate the trivially false ; the formal-conjectures statement, which counts with the site, takes . No text of the poser lets exceed , so the defect is the site's. The site's universal question against Erdős's "for some" is the site's own restatement and stands; Formulation records Erdős's wording with its answer. The change moves no standing: both questions of the corrected Statement are open, and no result about the site's wording beyond the trivial failure above is recorded.