Corroborate

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.

Problem as stated at github.com/google-deepmind/formal-conjectures/blob/34ee0e3c5fd52d202d62a71094a37970cb5fb870/FormalConjectures/ErdosProblems/151.lean. The claim text is written by Corroborate; that site has not reviewed or endorsed it.

The problem, as stated in formal-conjectures (Apache 2.0):

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

References formal-conjectures lists for this problem (a starting point, not evidence):

Verdict: no verdict yet

Evidence for

None yet.

Evidence against

None yet.