Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For k≥ 2, let χ_k be the largest chromatic number of a graph that does not contain k cycles of consecutive lengths. Sudakov–Verstraëte's conjecture. For every integer k≥ 2, χ_k=k+1. The lower bound χ_k≥ k+1 follows from the complete graph…
Let G be a graph. Its biclique partition number is the minimum number of bicliques, that is, complete bipartite graphs, needed to partition the edge set of G. Its chromatic number chi(G) is the minimum number of stable sets in a partition…
Let n and k be positive integers, and let c:E(K_2kn)→ [k] be an edge-coloring such that every color class has the same number of edges. A perfect matching M of K_2kn has color-deviation measure f(M)=∑_i=1^k||c^-1(i)∩ M|-n|. Almost…
All graphs under consideration are finite and simple. For a graph G and a vertex v, let d_G(v) denote the degree of v. Dean's conjecture. For every integer k ≥ 3, every graph with minimum degree at least k contains a cycle of length…
Conjecture Let (a_0,a_1,a_2,…,0) be a sequence of nonnegative integers which strictly decreases until 0. Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus i with a_i crossings, but not with…
Determine which graphs admit such a graph labeling. For such graphs, determine the minimum number of labels required.
Given a sign vector ε∈-1,1^k, can the least prime p satisfying (p_i/p)=ε_i for every i≤ k be found in deterministic polynomial time?
For fixed k, determine the largest d=d(k) for which the asymptotic K(d)-family bound |\mathcal G|\le(1+o(1))\binom{n-1}{k-1} holds, and extend that bound to the exact extremal result.
Let G=(V,E) be a finite loopless graph (multiple edges permitted). Two edges are adjacent if they share an endpoint. A proper edge coloring of G with color set C is a map ccolon E→ C such that c(e)≠ c(f) whenever e and f are adjacent. The…
For a graph Γ and an integer n≥ 2, let B_nΓ be its graph braid group and let H_1(B_nΓ) be its first homology group. Planarity–torsion conjecture. For every n≥ 2, the graph Γ is planar if and only if H_1(B_nΓ) is torsion-free. The…
Let M be a finite simple rank-3 matroid on n points with real weights a_i whose total sum is non-negative. Is the subconfiguration of non-negative-weight points connected by the lines whose weights are non-negative? More generally, for a…
Let T be a tree, and let J_T be its binomial edge ideal in S=K[x_1,…,x_n,y_1,…,y_n]. Denote by #internal vertices of T the number of internal vertices of T, and let Jewel be the tree depicted in the source paper. Jewel characterization…
Let P_n be the path graph on n vertices, let P_n^2 denote its square, and let β_k(k+r) be the unique nonzero Betti number of the (r-1)-dimensional shellable cut complex 4Δ_k(P_k+r^2)4 for the squared path, where r≥ 3. Diagonal recurrence…
Let m≥ 2. The digraph cal D^*_m has components cal A^*_m and cal B^*_m, where cal B^*_m consists of components cal B^*(1)_m,…,cal B^*(⌊ m/2⌋)_m ordered by nonincreasing vertex cardinality. Component-structure conjecture. The digraph cal…
Is complete integer factorization C_5 in deterministic polynomial time P?
Let G and G' be 3-connected graphs related by a twist along a minimal 4-vertex cut; minimality means that no proper subset of the four vertices already separates the graph. Twist invariance conjecture. Then N_2(G)=N_2(G'). Together with…
Let S be a set of n points in mathdsR^d in strong general position, and let G_T[S,r] be its Tverberg r-partition graph. Write δ(G_T[S,r]) for the minimum degree of this graph, and let Tv(d,r)=(d+1)(r-1)+1. For n>Tv(d,r), the minimum-degree…
Let G be a graph with k≥ 1 pendant vertices and chromatic number χ(G) satisfying k≥ χ(G)-1. The graphs K(2;a,b), caterpillar graphs in the cited theorem, Ct(3;n_1,0,n_3), and the indicated corona graphs P_m⊙ O_n, C_m⊙ O_n, and K_m⊙ O_n are…
(3) Persi Diaconis: "Say you play the explorers game [16] on a circle with n vertices labeled cyclically 0 through n − 1 and you repeatedly explore from 0. The probability that the last point occupied before the circle is filled is j is…
Let G be an isolate-free graph of order n, and let γ_g(G) denote the game domination number, the number of vertices selected when Dominator starts and both players play optimally. Kinnersley–West–Zamani's 3/5-conjecture. One should have…