Problem Statement
For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ (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$?
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$?
Categories:
Graph Theory
Progress
A problem of Erdős, Gallai, and Tuza [EGT92], who proved that\[\tau(G) \leq n-\sqrt{2n}+O(1).\]This would be best possible, since there exist triangle-free graphs with all independent sets of size $O(\sqrt{n\log n})$, which follows from the lower bound for $R(3,k)$ by Kim [Ki95] (see [165]).Indeed, Erdős, Gallai, and Tuza speculate that if $f(n)$ is the largest $k$ such that every triangle-free graph on $n$ vertices contains an independent set on $f(n)$ vertices, then $\tau(G)\leq n-f(n)$.
A positive answer to this problem would follow from a positive answer to [151] (since Ajtai, Komlós, and Szemerédi [AKS80] have proved that the $H(n)$ defined there satisfies $H(n)\gg \sqrt{n\log n}$).
See also [151], [611], this entry and and this entry in the graphs problem collection.
Source: erdosproblems.com/610 | Last verified: January 15, 2026