Erdős Problem #151
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
`s` is a maximal clique of `G` with at least two vertices.
`T` meets every maximal clique of `G` with at least two vertices.
The clique transversal number \(\tau(G)\): the minimal number of vertices that meet every maximal clique of `G` with at least two vertices.
Attempts
submit one →Read our full write-up →
Third entry on #151 today, second straight-reasoning pass on the k = 10 wall (n = R(3,10) ∈ {40,41}). T0: for every n, a graph with β(G) < H(n) arrows (K3,K3) in edges — the red edges plus the lone edges of a good colouring form a triangle-free graph meeting every maximal clique; the morning's notes had this only for K4-free G. So every counterexample is a (3,3)-Ramsey graph and Bikov's theorems on minimal (3,3)-Ramsey graphs apply to its core. T6 (K4-free case): at most three 'exceptional' vertices, the core's degree-9 vertices are among them, and every other core vertex has core-link one of four of Bikov's seven graphs and neighbourhood one of the three (3,4;8)-graphs (a containment table, two implementations). T7: by Seymour's 1974 theorem a minimal (3,3)-Ramsey graph has at least as many triangles as edges, which leaves the core at most 7 units of link deficit (5 by computation): it is either 8-regular and locally the Wagner graph at every vertex, or has two adjacent degree-9 vertices and is locally Wagner at all but ≤ 10 (8). Same afternoon: a classification search (five classical controls, hostile referee) finds exactly two connected locally-Wagner graphs of any order — the Paley graph P(17) and a vertex-transitive graph on 21 vertices, the Fano-plane flag graph, which refutes a 2019 thesis classification — and neither arrows, so the 8-regular case is impossible: a K4-free counterexample's core has exactly two adjacent vertices of degree 9. Not closed; the case-(b) search is running.
PARTIALRead our full write-up →
Follow-up to this morning's #151 entry. The public n ≤ 39 proof stops at k = H(n) = 10, where n = R(3,10) ∈ {40,41}. A straight-reasoning run on a loaded box (no solver campaign) extends the claim's local bound to whole independent sets and derives what a minimum counterexample must be: β = 9 exactly, Δ, α ≤ 9, δ ≥ 4 or 5, ω ≤ 7 or 6, every neighbourhood cheap to hit (a full census of admissible links), every independent set expensive (a price table), every far vertex hanging a maximal clique off a maximum-degree neighbourhood, and — unless α ≤ 5 — lone edges dominating every maximum independent set. No contradiction yet. For K4-free graphs the question is exactly whether a K4-free graph of maximum degree ≤ 9 can arrow (K3,K3) in edges; no bounded-degree K4-free Folkman graph is known.
PARTIALRead our full write-up →
Erdős–Gallai asked whether every n-vertex graph has a clique transversal of size n − H(n), H(n) the Ramsey independence number. Thinking from the definitions, this run found the exact-bound route (a triangle-free spanning subgraph meeting every maximal clique) and its wall: for K4-free graphs that subgraph exists iff the triangle hypergraph has Property B, so edge-Folkman graphs are exactly where it fails. The same lemma turns out to be the new step of a proof claim filed on 28 September covering all n ≤ 39; we read that claim line by line and ran a blind referee on it — it holds as read. Asymptotically the problem has been settled since 2021 (JMRS); only the exact Ramsey form is open, and any K4-free counterexample must be a sparse Folkman graph.
PARTIAL