Claim in Erdős problems: literature check, graph theory (1)
A published paper or arXiv preprint answers the main question of Erdős Problem #151 (theorem erdos_151 in formal-conjectures) in full (proof, disproof, or the exact value asked for) with no hypotheses beyond the problem's own.
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. 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, is \tau(G)\leq n-H(n)? Erdős remarked that this is perhaps completely wrongheaded [Er88].
- [Er88] Erdős, P., Problems and results in combinatorial analysis and graph theory. Discrete Math. (1988), 81-92.
- [EGT92] Erdős, P. and Gallai, T. and Tuza, Zs., Covering the cliques of a graph with vertices. Discrete Math. (1992), 279-289.
Verdict: no verdict yet
Evidence for
None yet.
Evidence against
None yet.