Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let Q_n) be the n-dimensional hypercube, with edge set E(Q_n), and consider a 2-colouring of its edges. Two vertices are antipodal if they differ in every coordinate. Feder–Subi conjecture. Every 2-colouring of E(Q_n) contains a path…
Let P be a simple polytope of dimension at least 3, and let P^* denote its dual polytope. For a subset S of the vertices of P, write conv(S) for its convex hull. Ziegler's conjecture. There exists a subset S of the vertices of P such that…
Let λ_| C^*(n) denote the maximum location-domination number of a twin-free, connected graph on n vertices. Garijo–González–Márquez conjecture. There exists a positive integer n_1 such that, for every n≥ n_1, λ_| C^*(n)=lfloorn/2⌋. Garijo,…
Let G be a graph with k vertices, let G_n=G× P_n, and let M be the integer B_k× B_k matrix from the theorem such that T_n=M^nv[1], where T_n is the number of spanning trees in G_n. Power-of-two factor degree conjecture. The characteristic…
Let A_1, …, A_100 be "cubes" in F_3^n (images of 0, 1^n under linear automorphisms). Is A_1 + … + A_100 = F_3^n?
Can every d-regular graphing without multiple edges be properly edge-colored by d+1 colors?
Understand and control how the shape of a polynomial affects Coppersmith-type small-root algorithms.
Let G be a finite simple graph. Its circumference c(G) is the length of a longest cycle, its induced circumference c'(G) is the length of a longest induced cycle, and δ(G) denotes its minimum degree. A graph is 2-connected if it remains…
Given a set of zero forcing sets can we transform one set into another using basic operations (vertex swaps, adding/deleting, token sliding and jumping, etc.) and stay within the set? In particular, if the given set is the set of all…
In a graph G=(V,E) with a root node r, two spanning trees T_1 and T_2 are called edge-independent if for any node x in V-r, the unique paths between r and x in T_1 and T_2 are edge-disjoint. Is it true that if G is k-edge-connected then…
Problem Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth?
Let τ be a spherical triangulation whose vertices have degree 5 or 6. A cycle in τ is bad if it has length l and separates two vertices of degree greater than l in τ. A cone-type triangulation at a vertex v is a triangulation in which…
Let C_n^2k denote the 2k-th power of the cycle C_n. Let G be a 2k-connected graph of order n. Dankelmann–Swart–Oellermann conjecture. sdiam_k(G)≤ sdiam_k(C_n^2k). This conjectures that the 2k-th power of the cycle maximizes the Steiner…
Let G be an abelian group, and let A,B⊆ G be finite sets with #A=#B. Let M(A,B) be the set of matchings from A to B, and let F^(t)_(A,B) be the final nonempty set in the iterative acyclicity construction, where t is the acyclicity index of…
Let G be a graph of order at least three, and write ω(G∖ S) for the number of components of G∖ S. A connected 2,4 -factor is a connected spanning subgraph whose vertex degrees all belong to 2,4 . The connected 2,4 -factor conjecture. If…
For a 1× n strip of stamps, let M(n) be the maximal number of ways to fold the strip over all mountain-valley assignments. Maximal-folding asymptotic conjecture. As n→∞, M(n)~ frac2^nn^5/4. The source says this behavior is suggested by…
For A⊆ 1,…,n let G(A) be the graph with vertex set A, where two integers are joined by an edge if they are coprime. Is it true that if lvert Arvert >lfloorn/2⌋+lfloorn/3⌋-lfloorn/6⌋ then G(A) contains all odd cycles of length ≤ n/3+1? Is…
Let L_n denote the Morse link numbers, and let ξ_5 denote the 5-adic valuation. Let α=dotsc 111111120_5 be a 5-adic integer. Postnikov's 5-adic valuation conjecture. For n≥ 4, ξ_5(L_n)= 2 if n is even, ξ_5(n-α)+3 if n is odd. This is…
Let G be a graph and let (α,β) be a pair of integers with maxα,β>1. An (α,β)-modular decomposition is a modular decomposition of G with parameters (α,β). NP-completeness conjecture. For every (α,β) with maxα,β>1, finding an (α,β)-modular…
Let G=(V,E) be a minimally cal R_d-connected graph, meaning that G-e is not cal R_d-connected for every edge e∈ E(G). The graph K_d+2 denotes the complete graph on d+2 vertices. Edge-bound conjecture. One has |E|≤ (d+1)|V|-binomd+22, with…