---

Statement

P. 280, after Problem 2: "An interesting particular case of Problem 1 is to prove $\tau_C(G)\le n-r(n)$ for 'sparse' graphs; $K_4$-free ones, for instance. Concerning this, we pose the following question.

Problem 3. How large triangle-free induced subgraphs does a $K_4$-free graph $G$ on $n$ vertices contain?

The Erdős--Szekeres theorem [7] implies that $\alpha(G)\ge cn^{1/3}$ for some constant $c>0$, but perhaps the size of triangle-free subgraphs grows faster." (p. 281)

Here $\tau_C(G)$ is the clique-transversal number and, in Problem 1 (p. 280), $r(n)$ is the least independence number of a triangle-free graph on $n$ vertices; Problem 1 asks whether $\tau_C(G)\le n-r(n)$ for all graphs on $n$ vertices.

Source. P. Erdős, T. Gallai and Zs. Tuza, Covering the cliques of a graph with vertices, Discrete Math. 108 (1992), 279--289, doi:10.1016/0012-365X(92)90681-5; printed pp. 280--281 = PDF pp. 2--3 of the publisher's scan, read on the page images. The edition is identified in the source digest.

Read depth. Claims checked: the passage was read clause by clause on the page images. It poses a question and proves nothing; the paper does not cite Erdős and Rogers (1962) for it.

Bears on

• Problem 620: the site's second source key and the source of the site's wording ("how large a triangle-free induced subgraph must $G$ contain?"); the paper connects the question to clique transversals of $K_4$-free graphs.