Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For unit-disk packings in the Euclidean plane, how much can the density differ from the triangular-lattice maximum while retaining analogous structure; in particular, if centers at distance at most 2+\varepsilon are joined, must the…
Let f(z) be an entire transcendental function. Does there exist a path L so that, for every n, lvert f(z)/z^nrvert → ∞ as z→ ∞ along L? Can the length of this path be estimated in terms of M(r)=max_lvert zrvert=rlvert f(z)rvert? Does there…
Let a finite Goldbach graph be a finite graph associated with Goldbach representations, and let a finite near Goldbach graph be a finite graph obtained from the corresponding near Goldbach construction. Bounded-diameter conjecture for…
Quantify elliptic curves over finite fields whose group order has a large prime divisor.
Let K_n be the complete graph and let F⊆ E(K_n). A proper K_6,K_6,6-sequence is the sequence construction defined in the source using copies of K_6 and K_6,6; write C_≤ t for the union of its edge sets. Four-dimensional rank conjecture.…
Let V(kΛ_0) be the integrable highest weight widehatsl(n)-module, with n≥ 2 and k≥ 1. A maximal dominant weight is a dominant weight in V(kΛ_0) that is maximal with respect to subtraction of positive roots. Enumeration conjecture. For…
Let G be a connected bipartite graph. A two-colored γ-set of G is a minimum dominating set D∈ underlineMDS(G) that can be partitioned as D=D_1∪ D_2 with V(G)-N_G[D_1]=D_2, V(G)-N_G[D_2]=D_1. Hartnell's characterization. If V(G) can be…
Is there a function f : N2 Ñ N such that every finite graph G of chromatic number at least f pr, kq satisfies one of the following two conditions: (1) G has a subgraph of chromatic number at least k and girth greater than r; (2) The…
Let D=(V,A) be a digraph whose underlying graph is k-partition-connected, and let r_0 ∈ V be a node of in-degree 0. Suppose that the in-degree of every other node is at least k. Is it true that D can be decomposed into k weakly connected…
Let G be a bipartite graph. For κ_0≥ 5, let H_κ_0,κ_0 be a largest induced crown graph in G, and let R(G) denote the representation number of G. Crown-subgraph conjecture. The representation number of G equals either ⌈κ_0/2⌉ or ⌈1+κ_0/2⌉.…
Let K_n,n be the complete bipartite graph with n vertices in each part, and let HG(G) denote the hat-guessing number of a graph G. For n≥ 3, the conjectured bound is Complete bipartite hat-guessing conjecture. HG(K_n,n)≤ n. This…
Call a finite simple graph Γ vertex-transitive if its automorphism group acts transitively on V(Γ), and call a cycle in Γ Hamiltonian if it passes through every vertex of Γ exactly once. For a cubic graph X (every vertex of degree 3), let…
Let X be a collection of subsets defining the class of X-matroids, and suppose that this class is nonempty. Let v_X be the function constructed from the sequence (val_X^n)_n∈N. A set function is submodular if it satisfies v_X(A)+v_X(B)≥…
Does every bridgeless graph have a nowhere-zero 5-flow?
Given an undirected graph G=(V,E), find a maximum cardinality 2-matching containing no cycles of length 4 in polynomial time.
Problem 1. Find a good characterization for undirected graphs having an acyclic orientation so that the in-degree of every node is even. Problem 2. Find a good characterization for undirected graphs G=(V,E) and T⊆ V, having an acyclic…
Let G be a d-regular graph of order n, and let m(H,k) denote the number of vertices of degree k in a spanning subgraph H. Asymptotic degree-balance conjecture. For every d there is a finite family D_d of exceptional graphs such that every…
A tournament is r-strong if deleting fewer than r vertices leaves a strongly connected tournament, and its minimum in-degree and minimum out-degree are the least in-degree and out-degree among its vertices. A tournament is k-linked if, for…
Let T be a tree on n eq 3 vertices, let k be a positive integer, and let d4ae_T be the order-k Steiner distance hypermatrix of T, whose (v_1,d7e2,d7e3,d7e4,d7e5,d7e6) entry is the Steiner distance d_T(v_1,d7e2,d7e3,d7e4,d7e5,d7e6). Its…
Let N be a rooted phylogenetic network on leaf set X. The quantities ℓ(N) and e(N) measure, respectively, the tree-based proximity of N and the minimum number of directed edges that must be added to make N tree-based. Edge-addition…