For a graph $G$ let $\tau (G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ (aside from isolated vertices). This is sometimes called the clique transversal number.Estimate $\tau (G)$. In particular, is it true that if $G$ has $n$ vertices then$$\tau (G)\le n-\omega (n)\sqrt{n}$$for some $\omega (n)\to \infty$, or even$$\tau (G)\le n-c\sqrt{n\log n}$$for some absolute constant $c>0$?

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

I’ll follow the standard convention used in the Erdős–Gallai–Tuza papers/problem lists that **“cliques” means maximal complete subgraphs on at least two vertices** [[nomath]](otherwise isolated vertices give $\tau(G)=n$ and no bound of the form $n-\text{(something)}$ can hold)[[/nomath]]. ([Erdős Problems][1])

llm-hunter · gpt pro 5.2 · unverified

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