Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let k be a positive integer, y_1,…,y_k complex numbers which are linearly independent over Q, α_1,…,α_k nonzero complex numbers and s_0,s_1,t_0,t_1,u positive real numbers satisfying max1,t_0,2t_1 < mins_0,2s_1 and maxs_0,s_1+t_1 < u <…
A solid brick is a brick with no nontrivial separating cut, and a graph is odd-intercyclic if every two odd cycles have a common vertex. A graph is cubic if every vertex has degree three. Cubic solid-brick conjecture. Every cubic solid…
Let F be a forest on n vertices, and let f(F)=f_2(F) denote the minimum number of vertices that must be deleted to obtain an induced subgraph with at least two vertices attaining its maximum degree, or with fewer than two vertices. Forest…
Let cal C_1 be the set of graphs isotopic to planar graphs, cal C_2 the set of graphs isotopic to graphs obtained from planar graphs by the specified moves, cal C_3 the set of graphs isotopic to graphs obtained from knots, including the…
For instance, it is still an open question to characterize all graphs H such that t(H, Gw ) \geq 0 for all weighted graphs Gw [Lov]. X t(f, G) = c\phi p∗ (x1 (\phi), y1 (\phi), . . . , xk (\phi), yk (\phi)) \phi
How many chambers are there for transportation polytopes for n× n matrices? For example, how many Ehrhart polynomials are needed?
We conjecture that the following stronger result holds. As alluded to above, Conjecture 5 would be implied by a conjecture of Thomassen [3], stating that every graph of large average degree contains a subgraph of large girth and average…
For a positive integer n, consider all ways of splitting 1,2,…,2n into two complementary sets A=a_1,…,a_n and B=b_1,…,b_n, i.e. A∩ B=∅, A∪ B=1,2,…,2n, and |A|=|B|=n. For such a splitting and an integer k with -2n≤ k≤ 2n, let…
Let G≠ C_n be a graph, and let c(G) denote its cyclomatic number. The quantity L_1(G) is the parameter used in the mixed metric dimension bound, and mdim(G) denotes the mixed metric dimension of G. Mixed metric dimension conjecture.…
Let N_m(g) denote the number of numerical semigroups S with multiplicity m(S)=m and genus g(S)=g. Kaplan's conjecture. For any m≥ 2, we have N_m(g)≤ N_m(g+1). This refines the genus-counting problem by fixing the multiplicity; the supplied…
Let T be a finite 3-coloured tournament, meaning a tournament whose edges are coloured with at most three colours. A tournament is a T_3 if three of its vertices span a non-transitive tournament whose three edges have distinct colours.…
If A is a set of n integers, what is the maximum number of affine translates of the set 0, 1, 3 that A can contain?
Let G be a bridgeless graph with m edges, and let the length of a cycle cover be the sum of the lengths of all cycles in the cover. Short Cycle Cover Conjecture. Every bridgeless graph with m edges has a cycle cover of length at most 1.4m.…
Let G=CS_k,n-k be a cycle-star graph, where k is the cycle order and n-k is the number of leaves. The edge irregularity strength es(G) is the least positive integer s for which there is a vertex labeling φ:V(G)→1,2,…,s such that the sums…
Let Y_n denote the set of Young diagrams with n boxes, and let s_λ be the Schur symmetric function indexed by λ. Let λ,hatλ∈ Y_n and μ,hatμ∈ Y_n-1 be pairs of Young diagrams such that both pairs differ by moving the box (i,j) to (hat i,hat…
Let F be a fixed field and let L ⊂ P^2_F be an arrangement of d lines. Its weak-combinatorics is the vector W(L)=(d;t_2,…,t_d), where t_i denotes the number of i-fold intersection points, with zero entries for i>m(L) omitted, where m(L) is…
Let NT(G) denote the Trinajstić index of a graph G. The conjecture concerns graphs attaining its minimum value. Trinajstić regularity conjecture. The minimum value of the Trinajstić index is 0, and being regular is a necessary but not…
Is there a finite set of unit line segments (rotated and translated copies of (0,1)) in the unit square, no two of which intersect, which are maximal with respect to this property? Is there a region R with a maximal set of disjoint unit…
Let R∈N^p, C∈N^q, and let M∈M_p,q(-1,0,1). For each integer i, let P_i(M) denote the set of cells at level i associated with M, and let C_i,i+1,k,k+1 denote the corresponding elementary 2×2 checkerboard move. Write A→A' for the switching…
Let G be a regular Bonnet-Myers sharp graph, and suppose the classification theorem for Bonnet-Myers sharp graphs assumes that G is self-centered. Regular-graph conjecture. For regular graphs, the self-centeredness condition in the…