Erdős Problems

Tags Prizes

0 solved out of 2 shown

OPEN

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

Estimate $\tau(G)$. In particular, is it true that if $G$ has $n$ vertices then \[\tau(G) \leq n-c\sqrt{n\log n}\] for some absolute constant $c>0$?

#610: [EGT92][Er94][Er99]

graph theory

A problem of Erdős, Gallai, and Tuza, who proved that \[\tau(G) \leq n-\sqrt{2n}+O(1).\]

This would be best possible, since there exist triangle-free graphs with all independent sets of size $O(\sqrt{n\log n})$, which follows from the lower bound for $R(3,k)$ by Kim [Ki95] (see [165]).

Indeed, Erdős, Gallai, and Tuza speculate that if $f(n)$ is the largest $k$ such that every triangle-free graph on $n$ vertices contains an independent set on $f(n)$ vertices, then $\tau(G)\leq n-f(n)$.

In [Er94] and [Er99] Erdős asks for a weaker upper bound $\tau(G) \leq n-\omega(n)\sqrt{n}$ for any $\omega(n)\to \infty$.

OPEN

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$.

#611: [EGT92][Er94][Er99]

graph theory

A problem of Erdős, Gallai, and Tuza [EGT92], who proved for the latter question that $k_c(n) \geq n^{c'/\log\log n}$ for some $c'>0$, and that if every clique has size least $k$ then $\tau(G) \leq n-(kn)^{1/2}$. Bollobás and Erdős proved that if every maximal clique has at least $n+3-2\sqrt{n}$ vertices then $\tau(G)=1$ (and this threshold is best possible).