Logo
All Random Solved Random Open
1 solved out of 12 shown (show only solved or open)
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$?

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

See also [611], this entry and and this entry in the graphs problem collection.

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

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

See also [610] and the entry in the graphs problem collection.

OPEN
Let $n\geq 3$ and $G$ be a graph with $\geq 2n+1$ vertices and $\binom{2n+1}{2}-\binom{n}{2}-1$ edges. Must $G$ be the union of a bipartite graph and a graph with maximum degree less than $n$?
Faudree proved that this is true if $G$ has $2n+1$ vertices.

See also the entry in the graphs problem collection.

OPEN
Let $r\geq 3$. For an $r$-uniform hypergraph $G$ let $\tau(G)$ denote the covering number (or transversal number), the minimum size of a set of vertices which includes at least one from each edge in $G$.

Determine the best possible $t$ such that, if $G$ is an $r$-uniform hypergraph $G$ where every subgraph $G'$ on at most $3r-3$ vertices has $\tau(G')\leq 1$, we have $\tau(G)\leq t$.

Erdős, Hajnal, and Tuza [EHT91] proved that this $t$ satisfies \[\frac{3}{16}r+\frac{7}{8}\leq t \leq \frac{1}{5}r.\]
OPEN
Let $r\geq 3$. If the edges of $K_{r^2+1}$ are $r$-coloured then there exist $r+1$ vertices with at least one colour missing on the edges of the induced $K_{r+1}$.
In other words, there is no balanced colouring. A conjecture of Erdős and Gyárfás [ErGy99], who proved it for $r=3$ and $r=4$ (and observered it is false for $r=2$), and showed this property fails for infinitely many $r$ if we replace $r^2+1$ by $r^2$.
SOLVED
For a triangle-free graph $G$ let $h_2(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $2$ and is still triangle-free. Is it true that if $G$ has maximum degree $o(n^{1/2})$ then $h(G)=o(n^2)$?
A problem of Erdős, Gyárfás, and Ruszinkó [EGR98]. Simonovits showed that there exist graphs $G$ with maximum degree $\gg n^{1/2}$ and $h_2(G)\gg n^2$.

Erdős, Gyárfás, and Ruszinkó [EGR98] proved that if $G$ has no isolated vertices and maximum degree $O(1)$ then $h_2(G)\ll n\log n$.

Alon has observed this problem is essentially identical to [134], and his solution in this note also solves this problem in the affirmative.

See also [619].

Additional thanks to: Noga Alon
OPEN
For a triangle-free graph $G$ let $h_r(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $r$.

Is it true that there exists a constant $c>0$ such that if $G$ is connected then $h_4(G)<(1-c)n$?

A problem of Erdős, Gyárfás, and Ruszinkó [EGR98] who proved that $h_3(G)\leq n$ and $h_5(G) \leq \frac{n-1}{2}$ and there exist connected graphs $G$ on $n$ vertices with $h_3(G)\geq n-c$ for some constant $c>0$.

See also [134] and [618].

OPEN
If $G$ is a graph on $n$ vertices without a $K_4$ then how large a triangle-free induced subgraph must $G$ contain?
A problem of Erdős, Gallai, and Tuza [EGT92]. The Erdős-Szekeres theorem (see [107]) implies that $G$ contains an independent set of size $\gg n^{1/3}$, so this is a lower bound.
OPEN
Let $G$ be a graph on $n$ vertices, $\alpha_1(G)$ be the maximum number of edges that contain at most one edge from every triangle, and $\tau_1(G)$ be the minimum number of edges that contain at least one edge from every triangle.

Is it true that \[\alpha_1(G)+\tau_1(G) \leq \frac{n^2}{4}?\]

A problem of Erdős, Gallai, and Tuza [EGT96], who observe that this is probably quite difficult since there are different examples where equality hold: the complete graph, the complete bipartite graph, and the graph obtained from $K_{m,m}$ by adding one vertex joined to every other.
OPEN
Let $G$ be a regular graph with $2n$ vertices and degree $n+1$. Must $G$ have $\gg 2^{2n}$ subsets that are on a cycle?
A problem of Erdős and Faudree. Erdős writes 'it is easy to see' that there are at least $(\frac{1}{2}+o(1))2^{2n}$ sets that are not on a cycle. If the regularity condition is replaced by minimum degree $n+1$ then the answer is no.
OPEN
Let $X$ be a set of cardinality $\aleph_\omega$ and $f$ be a function from the finite subsets of $X$ to $X$ such that $f(A)\not\in A$ for all $A$. Must there exist an infinite $Y\subseteq X$ that is independent - that is, for all finite $B\subset Y$ we have $f(B)\not\in Y$?
A problem of Erdős and Hajnal [ErHa58], who proved that if $\lvert X\rvert <\aleph_\omega$ then the answer is no. Erdős suggests in [Er99] that this problem is 'perhaps undecidable'.
OPEN
Let $X$ be a finite set of size $n$ and $H(n)$ be such that there is a function $f:P(X)\to X$ so that for every $Y\subseteq X$ with $\lvert Y\rvert \geq H(n)$ we have \[\{ f(A) : A\subseteq Y\}=X.\] Prove that \[H(n)-\log_2 n \to \infty.\]
A problem of Erdős and Hajnal [ErHa68] who proved that \[\log_2 n \leq H(n) < \log_2n +(3+o(1))\log_2\log n.\] Even the weaker statement that for $n=2^k$ we have $H(n)\geq k+1$ is open.

For this weaker statement, Erdős and Gyárfás conjecture the stronger form that if $\lvert X\rvert=2^k$ then, for any $f:P(X)\to X$, there must exist some $Y\subset X$ of size $k$ such that \[\#\{ f(A) : A\subseteq Y\}< 2^k-k^C\] for every $C$ (with $k$ sufficiently large depending on $C$).