Upper bound on clique transversal number

Let \( \tau(G)\) denote the cardinality of a smallest set of vertices in \( G\) that shares some vertex with every clique of \( G\).

Denote by \( R(n)\) the largest integer such that every triangle-free graph on \( n\) vertices contains an independent set of \( R(n)\) vertices. Is it true that \( \tau(G) \leq n -R(n)\)?

From the results on the Ramsey numbers \( r(3,k)\), we know that \( c \sqrt {n \log n} < R(n) < c' \sqrt {n \log n}\). So far, the best current bound [1] is \( \tau(G) \leq n- \sqrt{2n}+c\) for a small constant \( c\).

Erdös[2] asked the following additional questions on \( g(n)=\max \tau (G)\), where \( G\) ranges over all graphs on \( n\) vertices:


Is it true that \( \tau(G) < n-g(n) \sqrt n \) and \(g(n) \rightarrow \infty \) as \(n \rightarrow \infty\) ?

1 P. Erdös, T. Gallai and Zs. Tuza, Covering the cliques of a graph with vertices,Topological, Algebraical and Combinatorial Structures, Frolík's memorial volume, Discrete Math. 108 (1992), 279-289.

2 P. Erdös. Problems and results on set systems and hypergraphs, Extremal problems for finite sets (Visegrád, 1991), Bolyai Soc. Math. Stud., 3, pp. 217-227, János Bolyai Math. Soc., Budapest, 1994.