Problem 611

For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ (sometimes called the clique transversal number).

Is it true that if all maximal cliques in $G$ have at least $cn$ vertices then $\tau(G)=o_c(n)$ ?

Similarly, estimate for $c>0$ the minimal $k_c(n)$ such that if every maximal clique in $G$ has at least $k_c(n)$ vertices then $\tau(G)<(1-c)n$ .

Source: erdosproblems.com/611

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label. No source answering either question for arbitrary graphs was found in the search whose scope the Current assessment records. What Erdős, Gallai and Tuza give (Discrete Math. 108 (1992), refereed): for the second question, $k_c(n)\ge n^{c'/\log\log n}$ for some $c'>0$ and infinitely many $n$ (their Theorem 5: an infinite sequence of graphs whose cliques all have at least $n^{c/\log\log n}$ vertices with $\tau(G)\ge n-o(n)$ ) and, from their Theorem 2 ( $\tau(G)\le n-\sqrt{kn}$ when every clique has more than $k$ vertices, $n\ge k+2$ , the $5$ -cycle excepted), the elementary consequence $k_c(n)\le\lfloor c^2n\rfloor+2$ for large $n$ , written out below; so $k_c(n)$ lies between a slowly growing power of $n$ , along an infinite sequence of $n$ , and a linear function, and the paper itself says (p. 280) that "no upper bounds on $k(n)$ are known as sufficient conditions insuring a small clique-transversal number". For the first question the same theorem gives only a linear saving, $\tau(G)\le(1-\sqrt c+o(1))n$ when every clique has at least $cn$ vertices, and nothing found gives $o(n)$ for arbitrary graphs. Four further sources answer the first question, or give a constant-fraction bound, inside restricted graph classes only, as the Current assessment records: Tuza (1990) for strongly chordal graphs, where $\tau(G)\le n/r(G)$ with $r(G)$ the least order of a maximal clique, so cliques of at least $cn$ vertices give $\tau(G)\le1/c$ ; Bacsó, Gravier, Gyárfás, Preissmann and Sebő (2004) through clique colorings; Bacsó and Tuza (2009) for subcubic and claw-free graphs of maximum degree at most four; and Cooper, Grzesik and Král' (2018) for chordal graphs. None of them bears on arbitrary graphs. The site's third statement, that $\tau(G)=1$ once every clique has at least $n+3-2\sqrt n$ vertices, which the site and the paper call best possible, is attested by the paper's Note added in proof (p. 288: proved "with B. Bollobás in Oberwolfach, 1990", the threshold printed as $n+3-\lceil2\sqrt n\rceil$ ) with no published proof located; small graphs written out below witness its sharpness for $4\le n\le7$ . This is a bounded negative finding, not a certificate of openness.

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. The definition, p. 279; Problem 2 and the paragraph after it, p. 280; Lemma 1, p. 282; Theorem 2, p. 283; Theorem 5 and the Note added in proof, p. 288. Library home: Erdős, Gallai and Tuza 1992; paged at Erdős, Gallai and Tuza 1992, Problem 2 (p. 280 = PDF p. 2), Erdős, Gallai and Tuza 1992, Theorem 2 (p. 283 = PDF p. 5), Erdős, Gallai and Tuza 1992, Theorem 5 (p. 288 = PDF p. 10) and Erdős, Gallai and Tuza 1992, Note added in proof (p. 288 = PDF p. 10).
Er94: Erdős, P., Problems and results on set systems and hypergraphs. Extremal problems for finite sets (Visegrád, 1991), Bolyai Soc. Math. Stud. 3, János Bolyai Math. Soc., Budapest (1994), 217--227 (the site's reference text at /bibs/Er94, gives "(1994), 217-227. (MR 1319165)"; the volume and publisher from the graphs problem collection's bibliography). Not held: a 1994 volume chapter after the Rényi archive's cutoff (the archive's index, lists no paper after 1989), with no open copy identified. The graphs problem collection's page "SublinearCliqueTransversal" gives it as the source of the first question.
Er99: Erdős, P., A selection of problems and results in combinatorics. Combin. Probab. Comput. 8 (1999), 1--6. Not held; no open copy identified.
BoEr90: Bollobás, B., Erdős, P., Gallai, T. and Tuza, Zs., the theorem of the Note added in proof of [EGT92] ("we proved with B. Bollobás in Oberwolfach, 1990"); no publication of the proof was located, and the site credits it to Bollobás and Erdős.
Er61: Erdős, P., Graph theory and probability. II. Canad. J. Math. 13 (1961), 346--352; [EGT92]'s reference [6], the triangle-free graphs with small independence number that start the construction of Theorem 5. Library home: Erdős 1961 (context).
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 source of the $\langle t\rangle$ -property results for chordal and split graphs. Theorem 7, p. 123; Theorems 3 and 9, pp. 119--120 and 124--125; Proposition 10, p. 125. Library home: Tuza 1990.
BGGPS04: Bacsó, G., Gravier, S., Gyárfás, A., Preissmann, M. and Sebő, A., Coloring the maximal cliques of graphs. SIAM J. Discrete Math. 17 (2004), no. 3, 361--376, doi:10.1137/S0895480199359995. Theorem 4, p. 369; Theorem 7, pp. 371--374; Theorem 10, pp. 374--375. Library home: Bacsó et al. 2004.
BaTu09: Bacsó, G. and Tuza, Zs., Clique-transversal sets and weak 2-colorings in graphs of small maximum degree. Discrete Math. Theor. Comput. Sci. 11 (2009), no. 2, 15--24, doi:10.46298/dmtcs.453. Theorems 1 and 2, pp. 16--17. Library home: Bacsó and Tuza 2009.
CGK16: Cooper, J. W., Grzesik, A. and Král', D., Optimal-size clique transversals in chordal graphs. J. Graph Theory 89 (2018), no. 4, 479--493, doi:10.1002/jgt.22362; arXiv:1601.05305v2 (4 April 2018). Theorem 1 and Proposition 9, as numbered in the arXiv version. Library home: Cooper et al. 2016.

Problem 611

Status

Proof claims

Discussion