Problems

Seymour conjectured that every oriented graph has a vertex x with |N^++(x)| ≥ |N^+(x)|. It holds for oriented graphs of minimum out-degree exactly 7, the first improvement to the out-degree threshold since Kaneko and Locke settled degree 6…

VibeMathed records no statement for this problem. See erdosproblems.com for the original.

The interchange graph G(R,S) has the (0,1)-matrices with row sums R and column sums S as vertices, adjacent when they differ by a single 2× 2 interchange. Brualdi asked whether G(R,S) is always Hamiltonian. It satisfies more: it is…

For the Fubini numbers a(n), is a(n) = ∑_k=0^2^n-1-1 A284005(k) for every n > 0, as conjectured on the OEIS in 2018?

Every minimally generically globally rigid graph in R^d containing a subgraph isomorphic to K_d+2 is itself isomorphic to K_d+2, confirming Conjecture 6.3 of Garamvölgyi, Jackson and Jordán (2025).

WOW-284 asserts that the minimum dual degree of every connected graph of order at least three and girth at least five is at most the negative of its least distance eigenvalue. The paper refutes it with exact counterexamples of orders 38,…

Wellman and Pettie noted that the true leading constant for large-order Davenport-Schinzel sequences was known only to lie in an interval. The paper improves the Roselle-Stanton lower bound to match the pigeonhole upper bound in the…

For every n ≥ 2k + 1, is the independence polynomial of GP(n, k) real-rooted if and only if k is even? Exact Sturm counts refute both directions.

Campbell, Distel, Gollin, Harvey, Hendrey, Hickingbotham, Mohar and Wood conjectured that every graph of degree-d polynomial growth embeds into the strong product of d trees of linear growth and a bounded clique. False for d = 4: a…

White conjectured that the symmetric exchange binomials generate the toric ideal of a matroid. This is now known to be false; a rank 9 binary matroid constitutes a counterexample.

Hamaker and Reiner conjectured that the order complex of an open interval (u,w) in the ASM weak order is contractible unless w is the long element of a standard parabolic subgroup, in which case it is homotopy equivalent to a sphere.…

Let R(3;k) be the least n such that every k-colouring of the edges of K_n contains a monochromatic triangle. Determine lim_k→∞ R(3;k)^1/k (a $250 Erdős prize problem). A superexponential lower bound resolves the problem: the limit is…

For a finite connected graph G, let L_s(G) be the maximum number of leaves in a spanning tree and ℓ(G) the average local independence number. Must L_s(G) ≥ 2(ℓ(G) - 1)?

A graph G is maximal non-Hamiltonian if it is non-Hamiltonian but G + e is Hamiltonian for every nonedge e. In 1994 Vu Dinh Hoa conjectured a property of G - V(C) for a longest cycle C of such a graph. Disproved by an explicit base graph…

Let G be a simple connected graph on n≥ 5 vertices. If the maximum over all vertices v of ℓ(v) - the independence number of the subgraph induced by the open neighborhood N(v) - is at most 1, must G be well totally dominated? Answered…

Pak and Slonim conjectured that stretched Schubert structure constants are eventually polynomial. They are. Monomial coefficients in affine families of key and Schubert polynomials are eventually polynomial, and the Schubert duality of…

A cyclic coloration of a triangulation of a closed 2-manifold gives the faces around every vertex distinct colors. Chen and Lawrencenko made two conjectures about the cyclic chromatic number of minimal triangulations in 1999. Their second…

Sixteen previously unknown exact values, plus three that confirm the sibling theorem entries' predictions computationally, across five ordered-pattern families (P^alt, S^sc, C^mon, M^nest, K) under dihedral and reflective group actions -…

For every connected graph G, is α(G) ≤ ⌊ b(G) - log(ecc_avg(G)) ⌋, where b(G) is the largest induced-bipartite-subgraph order? An 11-vertex counterexample - a triangle with four leaves on each of two vertices - has α = 9 against bound 8.

Pach conjectured that n Jordan arcs, pairwise crossing exactly once with no triple points, have O(n) tangent pairs. The best known bound stood at O(n^7/4); the paper improves it to O(n^3/2) (and O(n^5/3) in the at-most-one-crossing…