Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Is the crossing number of the complete graph K_n equal to the value given by Guy's formula?
A honeycomb array is an arrangement of points on the triangular lattice satisfying the defining conditions described in the paper; two arrays are considered equivalent up to the symmetries of the hexagonal sphere. Completeness conjecture.…
Does there exist a universal constant \varepsilon>0 such that every graph G satisfies \chi(G)\leq\max_{v\in V(G)}\bigl((1-\varepsilon)(d(v)+1)+\varepsilon\omega(G[\widetilde N(v)])\bigr)?
Let G_n_n in mathbb N be a sequence of finite graphs with degrees bounded by d and such that lim_n→∞|V_n|=∞. Here, δ(G_n,p) denotes the minimum probability of error when reconstructing the initial common opinion from the limiting opinions,…
Conjecture 6. 5. (Seymour) Under the hypotheses of
Let P_t be the path graph on t vertices, C_t the cycle graph on t vertices, and K_2 the complete graph on two vertices. For a graph G, let γ_s(G) denote its protection number. Protection number conjecture. For any integer t≥ 2, γ_s(P_tBox…
Let R be a ring and let S be a proper non-commutative subring of R. The relative non-commuting graph Γ_S,R has chromatic index equal to its maximum vertex degree. Class 1 conjecture. The relative non-commuting graph Γ_S,R is of class 1.…
Let c_i(t) denote the number of times card i has been seen by time t. Eventual equality conjecture. For any card i, there exists t such that c_i(t)=c_1(t). This would make precise the observation that the numbers of times any two cards…
Let P be a path with vertex set V, and let (A_1,…,A_m) be a partition of V. Simultaneous deficit conjecture. There exists a subset S⊆ V independent in P such that |S∩ A_i|≥ |A_i|/2-1 for every i≤ m, with strict inequality holding for all…
Let G be a Berge graph, meaning a graph with no induced odd hole and no induced odd antihole. An antihole is the complement of a hole, and an odd prism is a prism whose three rungs all have an odd number of edges. A graph is…
Let A=(H,m) be an amoeba. An amoeba is immortal if it admits an infinite growth sequence, strongly immortal if every relevant growth process can continue indefinitely, and partially immortal if there is an infinite growth sequence from…
For ∈N and x∈N^n, a zero partition of x is a choice of signs σ∈-1,1^n such that ⟨x,σ⟩=0. Zero-partition maximization conjecture. If n is even, the number of zero partitions of x is at most the number for (1,…,1), namely binomnn/2. If n is…
Let S be a finite set of n items, with 0<d<n defective items, and let M(d,n) denote the minimum, over adaptive group-testing algorithms, of the worst-case number of tests needed to identify all defectives. Set r:=n/d. Hu–Hwang–Wang…
For every nontrivially unstable graph G, there exists an odd positive integer k such that G contains cycles isomorphic to both C_k and C_2k.
Let a 4MP be a 4-connected maximal planar graph, and let a linear Hamiltonian cycle be a Hamiltonian cycle such that the regions on one side of the cycle share edges with at most two other regions on that side; equivalently, the dual of…
A bouquet through O is a finite union C=C_1∪…∪ C_n of unit circles having the common point O. For a colouring of R^2, such a bouquet is smiling if some colour occurs on every circle C_i but does not occur at O. Smiling-bouquet conjecture.…
Let [n]=1,…,n, and let S⊆[n]^3 be a set that meets every line at most once. Write barS for the closure of S under the closure operation considered in the paper. Closure-size conjecture. There are constants c_1,c_2>0 such that, if…
Give efficient reductions in both directions between the degree-zero divisor-class-group discrete logarithm problem and the infrastructure discrete logarithm problem.
Let k and ℓ be integers with k ≥ ℓ ≥ 2. For graphs G and positive integers a_1,…,a_r, write G → (K_a_1,…,K_a_r) if every r-colouring of the edges of G contains a monochromatic copy of K_a_i in some colour i; write G not→ (K_a_1,…,K_a_r)…
For a graph G, let rm ind(G) be its number of independent sets, let d(u) be the degree of u, let rm iso(G) be the number of isolated vertices, and define Π(G)=2^rm iso(G)∏_uv∈ E(G)(2^d(u)+2^d(v)-1)^1/d(u)d(v). A vertex x∈ V(G) is good for…