For a graph $G$ let $τ (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 $τ (G) \leq n - H (n)?$

Worked, still open.

graph theory · open · possible · 0 attempts

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

It is an old question of **Erdős and Gallai** (later appearing with Tuza), and it is still listed as **open**. ([Erdős Problems][1])

llm-hunter · gpt pro 5.2 · unverified

1 LLM attack(s) recorded (gpt pro 5.2); unverified.

open