Problem 610

For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ (aside from isolated vertices). This is sometimes called the clique transversal number.

Estimate $\tau(G)$ . In particular, is it true that if $G$ has $n$ vertices then

\tau(G) \leq n-\omega(n)\sqrt{n}

for some $\omega(n)\to \infty$ , or even

\tau(G) \leq n-c\sqrt{n\log n}

for some absolute constant $c>0$ ?

Source: erdosproblems.com/610

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN), the site's label, whose suffix is a catalog label explained under Formalization; proved for both displayed questions: $T(n)=n-\Theta(\sqrt{n\log n})$ . The status-defining source is Corollary 2 of Joret, Micek, Reed and Smid (Electron. J. Combin. 28 (2021), P3.51, refereed and open access; the result and its acceptance evidence are recorded on the claim page Joret--Micek--Reed--Smid, from which the frontmatter is derived): every $n$ -vertex graph has clique chromatic number $O(\sqrt{n/\log n})$ , that is a coloring with that many colors in which no clique is monochromatic. The transfer to clique transversals is one line, written out below as an authored deduction: the complement of a largest color class meets every clique, so $\tau(G)\le n-\lceil n/\chi_c(G)\rceil\le n-c\sqrt{n\log n}$ for large $n$ and some $c>0$ , which answers the second question with $c$ and the first with $\omega(n)=c\sqrt{\log n}$ . The lower bound $T(n)\ge n-9\sqrt{n\log n}$ is Kim's Theorem 1.1 (1995, refereed) with the 1992 paper's Lemma 1(b). The 1992 paper's own bound is its Theorem 1, $\tau(G)\le n-\sqrt{2n}+\frac32$ . Three qualifications, each written out in the Current assessment: the site's "(LEAN)" suffix attaches to a company-hosted Lean file that declares the two theorems it uses (the 2021 corollary and Kim's theorem) with sorry, so it is a kernel-checkable derivation of the statement from unproved inputs and not a kernel-checked proof of the statement; the resolution reached the site through an unrefereed four-page note that a thread post credits to GPT-5.4 Pro, while the theorem it rests on is refereed (the note and the file are the pending claim on its own claim page (Przemek Chojecki, 2026)); and a thread post of 26 August 2026 reports that GPT-5.6 Sol claims a gap in the proof of Theorem 1 of the 2021 paper, from which Corollary 2 is derived, a report that gives no argument on the page, is examined by no published source and is unanswered on the thread beyond a note that the authors were contacted. The frontmatter keeps proved on the refereed theorem with these qualifications.

JMRS21: Joret, G., Micek, P., Reed, B. and Smid, M., Tight bounds on the clique chromatic number. Electron. J. Combin. 28 (2021), no. 3, Paper No. P3.51, 8 pp., doi:10.37236/9659 (submitted 19 June 2020, accepted 21 July 2021, published 10 September 2021; CC BY-ND); arXiv:2006.11353 (v1 19 June 2020, v2 25 August 2021; not held). Theorem 1 and Corollary 2, p. 2; the proof of Corollary 2, pp. 2--3; the proof of Theorem 1, pp. 3--7. Library home: Joret 2021; paged at Joret 2021, Theorem 1 (p. 2) and Joret 2021, Corollary 2 (p. 2).
EGT92: Erdős, P., Gallai, T. and Tuza, Zs., Covering the cliques of a graph with vertices. Discrete Math. 108 (1992), 279--289, doi:10.1016/0012-365X(92)90681-5. The definition, p. 279; Problem 1 and the expectation, p. 280; Lemma 1, p. 282; Theorem 1, p. 283; Theorem 3, p. 285. Library home: Erdős, Gallai and Tuza 1992; paged at Erdős, Gallai and Tuza 1992, Problem 1 (p. 280 = PDF p. 2) and Erdős, Gallai and Tuza 1992, Theorem 1 (p. 283 = PDF p. 5).
Ki95: Kim, J. H., The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$ . Random Structures Algorithms 7 (1995), 173--207; Theorem 1.1, typescript p. 1. Library home: Kim 1995; paged at Kim 1995, Theorem 1.1.
AKS80: Ajtai, M., Komlós, J. and Szemerédi, E., A note on Ramsey numbers. J. Combin. Theory Ser. A 29 (1980), no. 3, 354--360, DOI 10.1016/0097-3165(80)90030-8. Theorem 3, p. 358: $R(3,x)<100x^2/\ln x$ , from which the site's bound $H(n)\gg\sqrt{n\log n}$ follows by the elementary step recorded on its result page (the paper prints no bound on $H(n)$ ); used here as context only. Library home: Ajtai and Szemerédi 1980; paged at Ajtai and Szemerédi 1980, Theorem 3.
Er94: Erdős, P., Problems and results on set systems and hypergraphs. Extremal problems for finite sets (Visegrád, 1991), Bolyai Soc. Math. Stud. 3, János Bolyai Math. Soc., Budapest (1994), 217--227 (the site's reference text at /bibs/Er94, gives "(1994), 217-227. (MR 1319165)"; the volume and publisher from the graphs problem collection's bibliography). Not held: a 1994 volume chapter after the Rényi archive's cutoff (the archive's index, lists no paper after 1989), with no open copy identified. The graphs problem collection's page "CliqueTransversalUpperBound" attributes to it the question "Is it true that $\tau(G)<n-g(n)\sqrt n$ and $g(n)\to\infty$ as $n\to\infty$ ?" (its notation), the first question here.
Er99: Erdős, P., A selection of problems and results in combinatorics. Combin. Probab. Comput. 8 (1999), 1--6. Not held; no open copy identified.
Note26: A note on the clique-transversal number, a four-page note dated "April 21, 2026", with no author named in its text, hosted at https://www.ulam.ai/research/erdos610.pdf (; PDF metadata 21 April 2026). Theorem 1 ( $T(n)=n-\Theta(\sqrt{n\log n})$ ), Lemma 2 (the color-class transfer), Theorem 3 ([JMRS21] quoted), Corollary 4, Lemma 5, Theorem 6 ([Ki95] quoted), Corollary 7, Remark 8. The thread post that links it (21 April 2026) describes it as a short note by GPT-5.4 Pro. Not filed: it records consequences of [JMRS21] and [Ki95], quoting their theorems without proof; cited by URL and date.
Mo19: Molloy, M., The list chromatic number of graphs with small clique number. J. Combin. Theory Ser. B 134 (2019), 264--284; arXiv:1701.09133 (v1 31 January 2017, v2 29 June 2018). [JMRS21]'s reference [11], whose Theorem 1 is quoted as their Theorem 3 and whose proof theirs adapts; the thread's 18 May 2026 post points to it. Not held.
LMW23: Lichev, L., Mitsche, D. and Warnke, L., The jump of the clique chromatic number of random graphs. Random Structures Algorithms 62 (2023), no. 4, 1016--1034, doi:10.1002/rsa.21128; named in the thread as a paper whose proofs use the [JMRS21] bounds. Not held.
MSV26: Morris, R., Sahasrabudhe, J. and Verstraëte, J., On the Erdős--Rogers function. arXiv:2607.16118v1 (17 July 2026); named in the thread for the same reason; also a lead on Problem 620. Not held.

Problem 610

Status

Proof claims

Discussion