Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a graph, let χ_ℓ(G) denote its list chromatic number, and write G notsucceq K_s,t when G has no K_s,t minor. Woodall's list-colouring conjecture. For every s,t ∈ N, if G is a graph with G notsucceq K_s,t, then χ_ℓ(G) ≤ s+t-1. This…
For every integer t≥ 2 and every strictly increasing t-tuple of positive integers a_1<…<a_t, define a set recursively by A_0=a_1,…,a_t and, for each n≥ 0, adjoining the least positive integer that is neither already in A_n nor expressible…
Let T_n be a tree on n vertices and let F_m be the fan consisting of m triangles sharing a common vertex. For integers m≥ 6 and n≥ m^2-m+1, Zhang–Broersma–Chen conjecture. R(T_n,F_m)=2n-1. This conjecture extends the known exact result for…
For a finite simple graph G and a set S ⊆ V(G), let c(G - S) denote the number of connected components of the graph obtained from G by deleting S. For a real number t ≥ 0, call G t-tough if for every integer k > 1 and every S ⊆ V(G) with…
Let q be an alphabet size, and let E[D,q] denote the set of expansive networks on a digraph D over an alphabet of size q, while EA[D,q] denotes the set of abelian expansive networks on D over that alphabet. Sharp distinction conjecture.…
Hardness of Komlos Can we prove some hardness statement about finding a coloring achieving Komlos guarantee or the Banaszczyk discrepancy guarantee?
Let N be the net graph. Its binomial edge ideal is denoted by J_N, and write widehatreg(J_N) for its asymptotic regularity. Net graph asymptotic regularity conjecture. widehatreg(J_N)=3. The paper presents this as an example expected to…
Let local girth correspondence colouring refer to correspondence colouring with list sizes varying according to local girth. A hyperbolicity theorem is a theorem of the type used in the paper's main hyperbolicity result to control the…
Fix an integer q≥ 3. For an even sufficiently large integer n, let G be a random q-regular bipartite multigraph on n vertices, and let the number of its perfect matchings be considered modulo q. Perfect-matching residue conjecture. There…
For a valued field (K,v) of positive residue characteristic, with value group a Z-group or with divisible value group and large imperfect residue field, is there a simple useful additional assumption that ensures (K,v) is extremal? More…
Let c(n) be the minimum circumference of a connected vertex-transitive graph on n vertices, and let d(n) be the minimum circumference of a connected vertex-transitive digraph on n vertices. Asymptotic circumference conjecture.…
Let n≥ 2 and define pdreg(n)=(p,r)| there is a graph G over n vertices with pd(G)=p and reg(G)=r. Monotonicity conjecture. Let r,n≥ 2 be arbitrary integers. If (p,r)∈pdreg(n), then (p,r-1)∈pdreg(n). The preceding results show that the…
Investigate the convexity of zero forcing sets by creating a simplicial complex based on the complements of minimal zero forcing sets. Can the geometry of the complex tell us anything about propagation time or finding more minimal zero…
Let an n-permutation be a permutation of the entries 1,2,…,n, and let a block transposition interchange two adjacent blocks of entries. A series of such operations sorts a permutation if it transforms it into the increasing permutation 12……
Consider theorems about finite combinatorial structures that admit proofs by augmenting paths. Augmenting-path meta-conjecture. Such theorems should remain true in a structural form for infinite structures, possibly under some…
Let barK_n be an edgeless graph on n vertices. For each n ∈ N, define P^u_ℓ(barK_n,k) as the minimum, over all k-assignments L for barK_n, of the number P^u(barK_n,L) of equivalence classes of proper L-colorings under automorphisms of…
Let P_n(x;μ) be the row-generating polynomials of the Graham–Knuth–Patashnik recurrence, with parameters μ=(α,β,γ,α',β',γ') treated as indeterminates. Thus the coefficientwise partial order is taken in the seven variables x,α,β,γ,α',β',γ'…
Let G be a graph, with Randić index R(G), diameter d(G), and order #V(G). Aouchiche–Hansen's conjectured bound. R(G)≥ d(G)+√2-#V(G)+1/2. This is a proposed lower bound relating the Randić index to graph diameter. The supplied source does…
Conjecture Every digraph in which each vertex has outdegree at least k contains k directed cycles C_1, …, C_k such that C_j meets ∪_i=1^j-1C_i in at most one vertex, 2 ≤ j ≤ k.
Problem Determine wsat(K_n,Q_3).