Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let b_t,i(n) denote the number of hooks of length i in all t-regular partitions of n. Singh–Barman's conjecture. For every integer k 3, b_2,k(n) b_2,k+1(n) for all n 0 and ne k+1. This conjecture concerns the relative frequency of…
Let D=(d_1,d_2,…,d_t-1,d_t,1,…,1) be a degree sequence with d_t≥ 2 and d_2≠ 2, and let G be a unicyclic graph with degree sequence D. Define D'=(d_1,d_2,…,d_t-1-1,d_t-1,1,…,1) and let G(D') be the greedy tree with degree sequence D'. If…
Let k≥ 4 be an integer, and let G be a 3-connected non-bipartite graph with minimum degree at least k. Conjecture on consecutive cycle lengths. Except when G is K_k+1, the graph G contains k cycles of consecutive lengths. The paper proves…
Let G be a 2-connected cubic graph on n vertices. A circuit double cover (CiDC) is a finite family of connected 2-regular subgraphs of G such that every edge belongs to exactly two members of the family. Hušek–Šámal's conjecture. The graph…
For each n, let α_n be the cut-off value at which the Katz similarity index and effective resistance distance rankings for the path graph P_n change from agreeing to disagreeing. Cut-off convergence conjecture. The cut-off values α_n…
Let [k]=1,…,k, and consider the grid [k]^n. A coordinate line is the set of k points obtained by fixing all but one coordinate, and a marking of the lines designates one point on each line. Butler–Graham conjecture. There is a marking of…
Let T=(vecG,G,prec,A) be a twisted graph. A vector θ∈R^E respects prec when 0<θ_e<180 for all e∈ E and eprec f implies θ_e<θ_f. The graph T is constraining if, for some such θ, the system Σ(T)r>0 is not soluble and Σ(T)r=0 has a nontrivial…
For any fixed graph H, do H-free graphs contain large cliques or independent sets?
Let be a uniformly random permutation of [n], and let MHS_k denote the minimum number of max k-heapable subsequences into which can be partitioned. For each integer k, the normalized expected number of heaps is considered as n tends to…
What is the optimal strategy for two agents to meet on a network without communication?
Let r be a positive odd integer, let t satisfy 0≤ t≤ r, and let an r-t,t-factor be a spanning subgraph in which every vertex has degree either r-t or t. Akbari–Kano conjecture. Every r-regular graph has an r-t,t-factor. The conjecture was…
Let G be a graph on n vertices, with minimum degree δ(G). The S-game and D-game parameters are denoted by γ_rm SMB'(G) and γ_rm SMB(G), respectively. Improved SMBD-number bounds. (i) If γ_rm SMB'(G)<∞, then γ_rm SMB'(G)≤ lceiln/2⌉-δ(G)+1;…
Let G be a bridgeless graph, and let Φ_G(Q) denote its flow polynomial. The six-flow conjecture. For any bridgeless graph G, Φ_G(Q)>0 for Q∈[6,∞). The source presents this as a weaker conjecture motivated by the failure of the Welsh and…
A Markoff triple is a positive solution of x^2+y^2+z^2=3xyz. A Markoff number is an element of a Markoff triple. Let μ be the monoid homomorphism from 0,1^* to GL_2(Z) defined by μ(0)= 2 1 1 1 , μ(1)= 5 2 2 1 . For a matrix M, write M_12…
Let G be a graph, let α(G) denote its stability number, and let θ^(r)(G) denote the level-r semidefinite parameter in the theta hierarchy. Finite-convergence conjecture. For any graph G, θ^(r)(G)=α(G) for some r∈N. This is a weaker…
Let G be a graph, and let G^1/2 denote its 2-subdivision, obtained by replacing each edge with a path of length 2. Write γ_s(H) for the secure domination number of a graph H. Secure-domination lower-bound conjecture. For every graph G,…
(23) Farbod Shokrieh: "What is the full Gr¨ obner fan of the toppling ideal (as in [26])?"
Let b_2(G) denote the minimum dimension of a binary vector space in which the vertices of a graph G can be represented as an odd cover, and let K_m be the complete graph on m vertices. Odd-clique conjecture. For every integer n≥ 2,…
Let k≥ 4 and f_k(n) be the largest number of edges in a graph on n vertices which has chromatic number k and is critical (i.e. deleting any edge reduces the chromatic number). Is it true that f_k(n) ≫_k n^2? Is it true that f_6(n)~ n^2/4?…
Let an equiangular set have angle α=1/5 and base size K=4, and consider a (4,2) pillar and its Seidel graph. Finite-family conjecture for (4,2) pillars. In the case where α = 1/5 and base size K=4, there are only a finite number of…