Clique transversal vs. independence: is $\tau(G)\le n-H(n)$ for all graphs? (Erdős #151)
Statement
For a graph $G$ on $n$ vertices, the clique transversal number $\tau(G)$ is the minimum number of vertices meeting every maximal clique of $G$ that has at least two vertices (a maximal clique is an inclusion-maximal complete subgraph). Let $H(n)$ be the largest integer such that every triangle-free graph on $n$ vertices contains an independent set on $H(n)$ vertices. Is it true that every graph $G$ on $n$ vertices satisfies $$\tau(G)\le n-H(n)?$$
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else full written) that $\tau(G)\le n-H(n)$ for every $n$-vertex graph $G$; OR a counterexample — an explicit graph $G$ on $n$ vertices with a machine-verifiable computation of $\tau(G)$ (a certified minimum clique transversal) and of the relevant value of $H(n)$, exhibiting $\tau(G)>n-H(n)$. ADVANCES: prove the conjecture for a natural infinite subclass beyond triangle-free (e.g. $K_4$-free graphs, where Erdős and Gallai were stuck) with proof; OR improve the general bound $\tau(G)\le n-\sqrt{n}$ to $\tau(G)\le n-c\sqrt{n\log n}$, approaching $n-H(n)$, with proof; OR verify the inequality exhaustively for all graphs up to a new record vertex count with a reproducible program and an exhaustiveness certificate. Deliver the proof file, the counterexample plus certified $\tau$ and $H$ values, or the verification code plus certificate.
Background
A problem of Erdős and Gallai, listed in [Er88, p.82] and later as Problem 1 in Erdős–Gallai–Tuza [EGT92, p.280]. Elementary facts: $\tau(G)\le n-\sqrt{n}$ for every $G$, and if $G$ is itself triangle-free then $\tau(G)\le n-H(n)$ holds trivially (an independent set of size $H(n)$ omits at least one endpoint of every edge, and in a triangle-free graph every maximal clique is a single edge or vertex). The guaranteed triangle-free independence function satisfies $H(n)=\Theta(\sqrt{n\log n})$, from the Ramsey asymptotics $R(3,t)=\Theta(t^2/\log t)$. Erdős and Gallai could make no progress even under the added hypothesis that $G$ is $K_4$-free, and Erdős remarked that the conjecture is 'perhaps completely wrongheaded'. The general behaviour of $\tau(G)$ is the subject of erdosproblems.com/610, and the companion large-clique question is Erdős #611 (erdosproblems.com/611). Listed as open on erdosproblems.com/151 (fetched 2026-07-13, status 'open', tagged 'graph theory'). No Erdős prize is attached. The attacker's tool: exhaustive computer search over small graphs for a counterexample — compute $\tau(G)$ as a minimum hitting set (ILP) over the maximal cliques and compare against $n-H(n)$ using known values of the triangle-free independence function — together with structural arguments for restricted classes such as $K_4$-free graphs.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #151 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.