OPEN
This is open, and cannot be resolved with a finite computation.
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)?\]
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].
View the LaTeX source
This page was last edited 02 December 2025.
Additional thanks to: Zachary Chase
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #151, https://www.erdosproblems.com/151, accessed 2026-01-16
