{"data":[{"id":"erdos-gyarfas-1995","statement_oneline":"Every graph with minimum degree 3 contains a cycle whose length is a power of 2.","statement_full_latex":"Every finite graph with minimum degree at least $3$ contains a cycle of length $2^k$ for some $k \\ge 2$.","source":{"title":"Erdős-Gyárfás conjecture (Erdős prize problem)","arxiv":null,"url":"https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gy%C3%A1rf%C3%A1s_conjecture","year":1995,"area":"math.CO"},"renown":{"score":4,"rationale":"Carries an Erdős cash prize; the name alone draws attention. Proved for several classes (e.g. cubic planar); expert opinion on its truth is genuinely divided, unusual for a famous conjecture."},"attackability":{"score":3,"rationale":"Finite witness (a cubic-ish graph avoiding all power-of-two cycle lengths); the oracle (cycle-length spectrum) is exponential in principle but feasible to roughly 40 vertices; high-girth cubic graphs and cages are natural seeds since girth 5 kills C4 for free.","subscores":{"finite_witness":5,"oracle_cost":3,"freshness":2,"seedability":3}},"status":"open","last_verified_open":"2026-07-23","added":"2026-07-24","effective_status":"open","claims_count":0},{"id":"seymour-second-neighborhood-1990","statement_oneline":"Every oriented graph has a vertex whose second out-neighborhood is at least as large as its first.","statement_full_latex":"Every finite oriented graph (a digraph with no 2-cycles) contains a vertex $v$ with $|N^{++}(v)| \\ge |N^{+}(v)|$.","source":{"title":"Seymour's second neighborhood conjecture (posed c. 1990; see Dean-Latka)","arxiv":null,"url":"https://en.wikipedia.org/wiki/Second_neighborhood_problem","year":1990,"area":"math.CO"},"renown":{"score":4,"rationale":"A well-known conjecture of Seymour; proved for tournaments (Fisher 1996); the minimum out-degree 7 case was settled only in June 2026, the first threshold progress in two decades."},"attackability":{"score":3,"rationale":"Cheapest oracle on this board (two boolean matrix products), enabling enormous search volume; Guo-Kang-Zwaneveld (Apr 2026) supply seed structures (Seymour-tight orientations) and locate any counterexample near regular tournaments. Structured search reached 90% of vertices violating but the last few resist strongly.","subscores":{"finite_witness":5,"oracle_cost":5,"freshness":2,"seedability":4}},"status":"open","last_verified_open":"2026-07-23","added":"2026-07-24","effective_status":"open","claims_count":0},{"id":"vizing-1968","statement_oneline":"Domination numbers satisfy γ(G□H) ≥ γ(G)γ(H) for the Cartesian product of any two graphs.","statement_full_latex":"For all graphs $G$ and $H$, $\\gamma(G \\square H) \\ge \\gamma(G)\\,\\gamma(H)$, where $\\gamma$ denotes the domination number and $\\square$ the Cartesian product.","source":{"title":"Some unsolved problems in graph theory (Vizing)","arxiv":null,"url":"https://en.wikipedia.org/wiki/Vizing%27s_conjecture","year":1968,"area":"math.CO"},"renown":{"score":5,"rationale":"The central open problem of domination theory for six decades; active work as recently as July 2026 (constant-factor improvements by Steiner and by Aliabadi-Krop)."},"attackability":{"score":2,"rationale":"Finite witness (a pair of graphs) with an ILP oracle, but decades of minimal-counterexample theorems (no chordal or claw-free factors, factor domination numbers at least 4) fence the search into a hard region.","subscores":{"finite_witness":5,"oracle_cost":3,"freshness":1,"seedability":3}},"status":"open","last_verified_open":"2026-07-23","added":"2026-07-24","effective_status":"open","claims_count":0},{"id":"sidorenko-smallest-open-1993","statement_oneline":"Sidorenko's conjecture in its smallest unresolved instance: the bipartite graph K(5,5) minus a 10-cycle satisfies the Sidorenko density inequality.","statement_full_latex":"For the bipartite graph $H = K_{5,5} \\setminus C_{10}$ and every graph $G$, the homomorphism densities satisfy $t(H, G) \\ge t(K_2, G)^{e(H)}$. (Sidorenko's conjecture asserts this for every bipartite $H$; $K_{5,5} \\setminus C_{10}$ is the smallest case not covered by known results.)","source":{"title":"Sidorenko's conjecture (smallest open case)","arxiv":null,"url":"https://en.wikipedia.org/wiki/Sidorenko%27s_conjecture","year":1993,"area":"math.CO"},"renown":{"score":4,"rationale":"A major conjecture in extremal graph theory; a refutation of even this single instance would be front-page news in the field."},"attackability":{"score":2,"rationale":"A counterexample is a single weighted graph violating a density inequality, and homomorphism counting is differentiable, so gradient methods apply rather than only annealing. Widely believed true, and the continuous search space is unforgiving.","subscores":{"finite_witness":4,"oracle_cost":2,"freshness":1,"seedability":2}},"status":"open","last_verified_open":"2026-01-15","added":"2026-07-24","effective_status":"open","claims_count":0},{"id":"union-closed-frankl-1979","statement_oneline":"In any finite union-closed family of sets (other than the empty family), some element belongs to at least half the sets.","statement_full_latex":"If $\\mathcal{F}$ is a finite union-closed family of finite sets with $\\mathcal{F} \\ne \\{\\emptyset\\}$, then there exists an element $x$ belonging to at least $|\\mathcal{F}|/2$ of the sets in $\\mathcal{F}$.","source":{"title":"Union-closed sets conjecture (Frankl)","arxiv":null,"url":"https://en.wikipedia.org/wiki/Union-closed_sets_conjecture","year":1979,"area":"math.CO"},"renown":{"score":5,"rationale":"One of the most famous elementary-to-state open problems in combinatorics; Gilmer's 2022 breakthrough pushed the guaranteed constant to roughly 0.38, but 1/2 remains open."},"attackability":{"score":1,"rationale":"Finite witness in principle, but small cases are exhaustively settled, the post-Gilmer margin leaves little room, and the space of union-closed families explodes combinatorially; decades of hunting have found nothing. Listed as a trophy, not a recommendation.","subscores":{"finite_witness":4,"oracle_cost":3,"freshness":1,"seedability":1}},"status":"open","last_verified_open":"2026-01-15","added":"2026-07-24","effective_status":"open","claims_count":0},{"id":"min-order-line-graph-signature-2026","statement_oneline":"Determine the minimum order of a connected graph whose line graph has signature t, for each t at least 2.","statement_full_latex":"For each $t \\ge 2$, determine the minimum number of vertices of a connected graph $G$ with $s(L(G)) = t$. For $t = 2$: a 14-vertex example exists and is the unique subcubic example on at most 14 vertices, but no minimality claim over all connected graphs is known.","source":{"title":"The signature of connected line graphs is unbounded (Francis-Uptain)","arxiv":"pending","url":null,"year":2026,"area":"math.CO"},"renown":{"score":1,"rationale":"Posed July 2026 in the paper refuting the line-graph signature conjecture of Akbari, Elphick, Kumar, Pragada and Tang."},"attackability":{"score":4,"rationale":"Days old, essentially unhunted. Oracle is a single eigendecomposition; exhaustive search is complete for subcubic graphs through 14 vertices, leaving higher-degree small graphs and all t >= 3 wide open; the known 14-vertex and 48-vertex examples and the bridge/chain machinery are ready-made seeds.","subscores":{"finite_witness":5,"oracle_cost":5,"freshness":5,"seedability":4}},"status":"open","last_verified_open":"2026-07-24","added":"2026-07-24","effective_status":"open","claims_count":0},{"id":"txgraffiti-indep-domination-2020","statement_oneline":"For r-regular graphs (r at least 3), the independent domination number is at most the minimum maximal matching number.","statement_full_latex":"For every connected $r$-regular graph $G$ with $r \\ge 3$, $i(G) \\le \\mu^{*}(G)$, where $i$ is the independent domination number and $\\mu^{*}$ the minimum maximal matching (saturation) number.","source":{"title":"Machine-generated conjecture (TxGraffiti program), surveyed in 'In Reverie Together' (2025)","arxiv":"2507.17780","url":"https://arxiv.org/abs/2507.17780","year":2020,"area":"math.CO"},"renown":{"score":1,"rationale":"A specialist conjecture from automated conjecturing, open since 2020."},"attackability":{"score":4,"rationale":"Both invariants exactly computable by ILP at searchable sizes; generalized Petersen graphs sit on the equality ridge in large numbers, giving abundant seeds. A July 2026 structured search (several hundred exact evaluations plus ridge hill-climbing) found a wide equality plateau but no crossing, suggesting a hidden counting obstruction.","subscores":{"finite_witness":5,"oracle_cost":3,"freshness":3,"seedability":5}},"status":"open","last_verified_open":"2026-07-22","added":"2026-07-24","effective_status":"open","claims_count":0},{"id":"txgraffiti-zero-forcing-2017","statement_oneline":"For connected subcubic graphs other than K4, the zero forcing number is at most the independence number plus one.","statement_full_latex":"For every connected graph $G$ with maximum degree at most $3$ and $G \\ne K_4$, $Z(G) \\le \\alpha(G) + 1$, where $Z$ is the zero forcing number and $\\alpha$ the independence number.","source":{"title":"Machine-generated conjecture (TxGraffiti program), surveyed in 'In Reverie Together' (2025)","arxiv":"2507.17780","url":"https://arxiv.org/abs/2507.17780","year":2017,"area":"math.CO"},"renown":{"score":1,"rationale":"Known mainly within the automated-conjecturing community; highlighted in a 2025 survey as one of a handful of machine conjectures resisting both proof and counterexample."},"attackability":{"score":4,"rationale":"Finite witness with computable (NP-hard but small-scale feasible) invariants; subcubic graphs enumerate cleanly; a nine-year survival under active attention is the main warning sign.","subscores":{"finite_witness":5,"oracle_cost":3,"freshness":3,"seedability":3}},"status":"open","last_verified_open":"2026-07-22","added":"2026-07-24","effective_status":"open","claims_count":0}],"sort":"board","status":null,"notice":"Status is community- and machine-tracked and may lag. Verify independently before investing effort."}