Problems

Conjectures that every bridgeless graph has a collection of cycles covering each edge exactly twice.

For a sequence of n distinct reals, determine the largest constant c such that some monotonic subsequence always has sum exceeding (c-o(1))·(1/√n) times the total sum. Resolved as c = 1.

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

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)?

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…

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.

Albertson and Berman conjectured that for every simple planar graph G on n vertices, the largest vertex set inducing a forest has size at least n/2. The standing lower bound since the same year has been Borodin's 2n/5, from his acyclic…

For a connected graph G , let t= tree( G ) (order of a largest induced tree), A= average eccentricity, and L= maximum independence number of a neighbourhood. Then ⌈ (A+L)/3 ⌉ ≤ t. (The evenly-divided reading of the conjecture holds; a…

Determine the Shannon capacities of odd cycles beyond C_5, or improve the best explicit bounds. Lovasz's theta function settled C_5 in 1979 and every longer odd cycle has stayed open since. The current records, all obtained with model…

Is the number of nonnesting permutations of 1,1,…,n,n avoiding both 1132 and 3312 equal to 3^n - 3 · 2^n-1 + 1 for every n ≥ 1?

VibeMathed records no statement for this problem. See formal-conjectures PR #4668 - Mark WOWII Graph Conjecture 217 solved for the original.

Jaeger conjectured that every bridgeless cubic graph G admits a Petersen coloring: a map φcolon E(G)→ E(P) into the edges of the Petersen graph P such that, for every vertex v of G, the three edges at v are sent to three edges meeting at a…

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

If H is bipartite and r-degenerate, is ex(n;H) ≪ n^2-1/r (a $500 Erdős-Simonovits prize conjecture)? A counterexample refutes the degeneracy conjecture.

The multivariate independence polynomial is the partition function of the hard-core model with per-vertex fugacities. The paper proves a lower bound extending to the multivariate setting a result Tao proved in the univariate case, and…

Teschner conjectured that every finite simple graph G with at least one edge satisfies b(G) ≤ 3/2Δ(G), where b(G) is the bondage number and Δ(G) is the maximum degree. Yavari gives a connected cubic bipartite graph on 18 vertices with…

For positive integers d and k, let n_k(d) be the maximum order of a graph of maximum degree at most d and diameter at most k. It is shown that lim_d → ∞n_k(d)/d^k = 1 for every fixed k, thereby resolving the asymptotic degree-diameter…

With N = 2^k - 1 and wt(n) the binary Hamming weight, Tu and Deng conjectured that for every 1 ≤ t ≤ N-1 at most 2^k-1 pairs (a,b) satisfy a + b ≡ t pmod N and wt(a) + wt(b) < k. Proved in full.