Problem 151

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)?

Source: erdosproblems.com/151

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open. No proof, disproof or proof claim for the inequality was found in the search whose scope the Current assessment records. The best explicit upper bound valid for every $n$ is Theorem 3 of Erdős, Gallai and Tuza (Discrete Math. 108 (1992), refereed): $\tau(G)\le n-\sqrt{2n}+\sqrt2$ for every graph on $n$ vertices, from a linear-time algorithm; their Theorem 1 gives $n-\sqrt{2n}+\frac32$ by averaging two lemmas. The best asymptotic bound is $\tau(G)\le n-c\sqrt{n\log n}$ for some $c>0$ and all large $n$ , Corollary 2 of Joret, Micek, Reed and Smid (2021) with the one-line transfer recorded on Problem 610. The conjectured value is $n-H(n)$ with $H(n)$ of order $\sqrt{n\log n}$ : the 1992 paper records $c_1\sqrt{n\log n}\le H(n)\le c_2\sqrt n\log n$ from Ajtai, Komlós and Szemerédi (1980, refereed; their Theorem 3, $R(3,x)<100x^2/\ln x$ , the bound on $H(n)$ being its elementary rewriting) and Erdős (1961), and Kim's Theorem 1.1 (1995) gives $H(n)\le9\sqrt{n\log n}$ for large $n$ . The 1992 authors write that "so far we could not construct examples worse than triangle-free ones" ([EGT92], p. 280), and Erdős that the conjecture "is perhaps completely wrongheaded". The asymptotic bound matches the order of $n-H(n)$ but not its constant, so it leaves this problem open. This is a bounded negative finding, not a certificate of openness. The inequality holds for every chordal graph, by Tuza's bound $\tau(G)\le n/2$ for chordal graphs (Discrete Math. 86 (1990), Theorem 2(a), refereed), an accepted partial claim recorded on its claim page (Tuza, 1990). A partial proof claim of 2026-09-28, the inequality for every graph on at most 39 vertices, is on the site's proof-claim tab; it is recorded as claimed on its claim page (veljjanoski, 2026) and derives nothing for the standing, which stays open.

EGT92: Erdős, P., Gallai, T. and Tuza, Zs., Covering the cliques of a graph with vertices. Discrete Math. 108 (1992), 279--289, doi:10.1016/0012-365X(92)90681-5; received 4 January 1991. The definition, p. 279; Problem 1 and the paragraph after it, p. 280; Problem 3 and the $\langle t\rangle$ -property, p. 281; Lemma 1, p. 282; Theorem 1, p. 283; Theorem 3, p. 285. Library home: Erdős, Gallai and Tuza 1992; paged at Erdős, Gallai and Tuza 1992, Problem 1 (p. 280 = PDF p. 2), Erdős, Gallai and Tuza 1992, Theorem 1 (p. 283 = PDF p. 5) and Erdős, Gallai and Tuza 1992, Problem 3 (p. 281).
Er88: Erdős, P., Problems and results in combinatorial analysis and graph theory. Discrete Math. 72 (1988), 81--92; Section 3, printed p. 82. Library home: Erdős 1988.
AKS80: Ajtai, M., Komlós, J. and Szemerédi, E., A note on Ramsey numbers. J. Combin. Theory Ser. A 29 (1980), no. 3, 354--360, DOI 10.1016/0097-3165(80)90030-8; [EGT92]'s reference [2]. Theorem 2, printed p. 355 (PDF p. 2 of the publisher's open-archive file): $\alpha(G)\ge0.01(n/t)\ln t$ for triangle-free graphs of average degree $t$ ; Theorem 3, printed p. 358 (PDF p. 5 of the same file): $R(3,x)<100x^2/\ln x$ , from which $H(n)\ge c_1\sqrt{n\log n}$ follows by the elementary step recorded on its result page (the paper prints no bound on $H(n)$ ). Library home: Ajtai and Szemerédi 1980; paged at Ajtai and Szemerédi 1980, Theorem 2 and Ajtai and Szemerédi 1980, Theorem 3.
Er61: Erdős, P., Graph theory and probability. II. Canad. J. Math. 13 (1961), 346--352; [EGT92]'s reference [6], the upper bound $H(n)\le c_2\sqrt n\log n$ (triangle-free graphs on $n$ vertices with no independent set of $[A\sqrt n\log n]$ vertices). Library home: Erdős 1961 (its card's account).
Ki95: Kim, J. H., The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$ . Random Structures Algorithms 7 (1995), 173--207; Theorem 1.1, typescript p. 1. Library home: Kim 1995; paged at Kim 1995, Theorem 1.1. Not a site key for this problem.
JMRS21: Joret, G., Micek, P., Reed, B. and Smid, M., Tight bounds on the clique chromatic number. Electron. J. Combin. 28 (2021), no. 3, Paper No. P3.51, doi:10.37236/9659; Corollary 2, p. 2. Library home: Joret 2021; paged at Joret 2021, Corollary 2 (p. 2). Not a site key for this problem; the Problem 610 source.
Tu90: Tuza, Zs., Covering all cliques of a graph. Discrete Math. 86 (1990), 117--126, doi:10.1016/0012-365X(90)90354-K; [EGT92]'s reference [11], the chordal-graph results; Theorem 2(a), p. 119. Library home: Tuza 1990. Claim page: Tuza 1990.
BGMTU25: Boros, E., Gurvich, V., Milanič, M., Tikhanovsky, D. and Uno, Y., Conformality of minimal transversals of maximal cliques. arXiv:2405.10789 (v2 20 June 2025, 34 pp.); and [MiUn24] Milanič, M. and Uno, Y., The upper clique transversal problem. arXiv:2309.14103 (v3 13 August 2024, 29 pp.). Adjacent literature on clique transversals (conformality of the family of minimal transversals; the largest minimal transversal); neither concerns Problem 1. Library homes: Boros 2025 and Milanič and Uno 2024.

Problem 151

Status

Proof claims

Discussion