Erdős Problem #151

declared status 'open'. Formalized: no. 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)?$$ Prize: no. Tags: graph theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.