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$ on at least two vertices (sometimes called the clique transversal number).
Let $H(n)$ be maximal such that every triangle-free graph on $n$ vertices contains an independent set on $H(n)$ vertices.
If $G$ is a graph on $n$ vertices then is\[\tau(G)\leq n-H(n)?\]
Let $H(n)$ be maximal such that every triangle-free graph on $n$ vertices contains an independent set on $H(n)$ vertices.
If $G$ is a graph on $n$ vertices then is\[\tau(G)\leq n-H(n)?\]
Categories:
Graph Theory
Progress
It is easy to see that $\tau(G) \leq n-\sqrt{n}$. Note also that if $G$ is triangle-free then trivially $\tau(G)\leq n-H(n)$.This is listed in [Er88] as a problem of Erdős and Gallai, who were unable to make progress even assuming $G$ is $K_4$-free. There Erdős remarked that this conjecture is 'perhaps completely wrongheaded'.
It later appeared as Problem 1 in [EGT92].
The general behaviour of $\tau(G)$ is the subject of [610].
Source: erdosproblems.com/151 | Last verified: January 13, 2026