Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a finite group, let Z(G) be its center, and let Υ_G be the simple graph whose vertices are the elements of G, with distinct vertices x and y adjacent when C_G(x)≠ C_G(y), where C_G(x) is the centralizer of x in G. A graph is…
Is it true that for n > sk, the chromatic number χ(KG_s(n,k)) = n - sk +s?
Let d≥ 3. A sequence of graphs (G_n) is said to have maximum degree at most d when every G_n has n vertices and maximum degree at most d. The size-Ramsey number hatr(G_n) is the minimum number of edges in a graph whose every edge-colouring…
Let π_1 be a graphic degree sequence, and let k denote the degree sequence in which every term is k. Two graphic degree sequences pack when they have realizations on the same vertex set with edge-disjoint edge sets. Rao–Rao k-factor…
Let a be a weak composition, let S(a) be the associated skew diagram, and let K_ S(a) be its skew polynomial. The skew-polynomial expansion conjecture. The skew polynomial expands as a nonnegative sum of Schubert polynomials. This places…
Let t>0, and let a minimally t-tough graph be a t-tough graph whose toughness decreases after deleting any edge. Katona–Varga's generalized conjecture. Every minimally t-tough graph has a vertex of degree ⌈ 2t⌉. The conjecture was…
Fix an n-cycle s and map every n-cycle q to its conjugate D(q) = q s q^-1, which is the same as reading the one-line word (q(0), …, q(n-1)) back as a cycle. Iterating D turns the (n-1)! n-cycles into a functional graph. Its only fixed…
Let G be a bridgeless cubic graph. Let ω'(G) denote its weak oddness and r(G) its resistance, using the definitions in the paper. Weak oddness versus resistance conjecture. One has ω'(G)≤ 2r(G). This conjecture compares two structural…
π(B_5,5)=40/81, and π(B_6,6)=frac12.
A poset has a planar diagram if its cover graph can be drawn in the plane with every cover relation represented by a curve directed upwards. Its cover graph is the graph whose vertices are the elements of the poset and whose edges join…
Let u be an element of the plactic monoid, let m=max u, and let ℓ be the number of rows of P(u). For w∈ C(u), write the rows of P(w) as R_i for i≥ 1. Strengthened row-maximum conjecture. For every i with 1≤ i≤ ℓ, max R_i≤ m. This would…
Let λ be a partition, and let Skeleton(λ) be the skeleton whose vertices are standard tableaux of shape λ. For each positive integer s, let H_s be the induced subgraph whose vertices are the standard tableaux with descent compositions…
Let G=(V,E) be an Eulerian graph with minimum degree at least 4, and let W be a closed Eulerian walk of G. Is it true that G has a cycle decomposition such that no pair of consecutive edges of W appear in the same cycle of the…
Let r≥ 3 be a rational number. For a graph G, let χ_c'(G) denote its circular chromatic index, and let CCHI^=_r be the decision problem of determining whether χ_c'(G)=r. DP-completeness conjecture. The problem CCHI^=_r is DP-complete. The…
Let k≥ 3, and let r_1,…,r_k be a set of distinct positive reals with r_1>…>r_k>0. A sequence over a k-element set is balanced if, for every symbol, the numbers of occurrences in any two contiguous subsequences of equal length differ by at…
The cochromatic number of G, denoted by ζ(G), is the minimum number of colours needed to colour the vertices of G such that each colour class induces either a complete graph or empty graph. Let χ(G) denote the chromatic number. If G is a…
Let G be a connected graph, and let D'(G) denote its distinguishing index and OD'^-(G) its negative oriented distinguishing index. Conjecture for distinguishing index two. If D'(G)=2, then OD'^-(G)=1. This is motivated by the preceding…
Let k and d be positive integers. For a graph G, call it (k,d)-sparse if every subgraph H satisfies (k+1)(k+d)v(H)-(k+d+1)e(H)-k^2≥ 0. Call a subgraph H (k+1)-overfull if e(H)>(k+1)(v(H)-1). Sparse Strong Nine Dragon Tree Conjecture. Every…
Let C be a Penrose caterpillar, let S be the graded poset of caterpillars used in the source, and let f_boat transform a Penrose caterpillar by replacing each relevant subpath along the hull of a boat with the corresponding subpath along…
For every x∈R let A_x⊂ R be a bounded set with outer measure <1. Must there exist an infinite independent set, that is, some infinite X⊆ R such that x ot∈ A_y for all x eq y∈ X? If the sets A_x are closed and have measure <1, then must…