Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be an infinite group generated by d elements. The main conjecture asserts that the product replacement graphs Γ_k(G) have exponential growth for all k≥ d+1. If these graphs are disconnected, this means that at least one connected…
Let P=(T;U,V) be a 3M-DAP. Write t,u,v for the relevant row lengths, s_t,s_u,s_v for the numbers of rows of types T,U,V, and x_t,x_u,x_v for their total values. A (T,V)-pair consists of subsets of T- and V-rows with sizes a and b. Type-1…
Let T be a caterpillar, let r≥ 1, and let a maximum r-center be a vertex z maximizing the number of independent r-sets containing it. Caterpillar center-neighbor conjecture. If z is a maximum r-center, then the neighbor of z has maximum…
A minimal brick is a brick G such that G-e is not a brick for every edge e∈ E(G). A brick is a bicritical and 3-connected graph, and a graph is bicritical if G-u,v has a perfect matching for every pair of distinct vertices u and v. Write…
Let hatR(G) denote the size Ramsey number, the minimal number of edges m such that there is a graph H with m edges such that in any 2-colouring of the edges of H there is a monochromatic copy of G. Determine hatR(K_n,n), where K_n,n is the…
Let L be a transitive permutation group. It is semiprimitive if each of its normal subgroups is either transitive or semiregular, and it is graph-restrictive if there exists a constant c(L) such that, for every connected locally-L pair…
Do there exist infinite families of (a,b,c,d,e)-regular graphs whose links of every order are connected, meaning the neighborhoods of every vertex, edge, triangle, K_4, and K_5 are connected?
Let G_n be an io-decomposable Riordan graph of the Bell type. The Pascal and Catalan graphs are PG_n=G_n(1/(1-z),z/(1-z)), CG_n=G_n(C(z),zC(z)). Here rm diam(G) denotes the graph diameter. Diameter extremality conjecture. For n≥4, 2=rm…
Let s(q):=∏_j=1^∞frac(1-q^2j)^21-q^j. Suppose that s(q)=∑_n≥ 0s_n q^n, is s_n≥ 0 for all n?
For an (n+1)-vertex graph G and a vertex v∈ V(G), write G∖v for the graph obtained by deleting v, and define f(n)=maxfracr(G)r(G∖v):G is an (n+1)-vertex graph and v∈ V(G). Polynomial sensitivity conjecture. There is some c>0 such that…
Let G_n be a sequence of connected graphs, each with n vertices and O(n^α) edges, where α<2 is fixed. Here P(G) denotes the probability that a uniformly chosen subtree of G is spanning. Chin et al.'s conjecture. Then lim_n → ∞P(G_n)=0.…
Give an algorithm and/or a good characterization to decide if a red-blue edge-coloured bipartite graph contains a perfect matching with exactly k red edges.
Let G=(V,E,w) be an edge-weighted graph with non-negative edge weights, and let w(G) denote the total edge weight. A bisection is a cut whose two parts differ in size by at most 1. Let k be a positive integer and suppose that Δ(G)≤ k.…
Let K_a_1,a_2,a_3,n denote the complete multipartite graph whose parts have sizes a_1,a_2,a_3,n, let K_2,4,n denote the complete multipartite graph with parts of sizes 2, 4, and n, and let cr(G) be the crossing number of a graph G. Let…
For integers n and k with k≥ 1 and n≥ 2k+1, let the bipartite Kneser graph H(n,k) have as vertices all k-element and all (n-k)-element subsets of [n]:=1,2,…,n, with an edge between two vertices exactly when one corresponding set is a…
Let a permutation perm be given together with positive integers numphase and numpile. In each of numphase rounds, the permutation may be shuffled using Dealer's choice on numpile piles, where the dealer chooses the pile assignment…
Let D be a digraph of order n. Write δ^0 for its minimum semidegree, and let γ_oso(D) and γ_iso(D) denote its open secure out-domination and secure in-domination numbers, respectively. Secure domination conjecture. If δ^0≥ 1, then…
Let hat r(G_1,G_2) be the least number of edges in a graph H such that every red-blue colouring of E(H) contains a red copy of G_1 or a blue copy of G_2. Let f(n) be the largest m for which some n-vertex graph G with m edges satisfies hat…
Let G be a finite abelian group, and let φ(G,n) denote its phylogenetic complexity at level n. Eventual constancy recurrence. φ(G,n+1)=max(2,φ(G,n)). The paper describes this as a strengthening of its theorem that φ(G,·) is eventually…
Let n ≥ 3, let 1 ≤ a_1 ≤ … ≤ a_n, and define e = #E(K_a_1, …, a_n-1). If a_1 + … + a_n-1 > 6 and a_n ≥ e, then the family-size stabilization conjecture asserts that |F(K_a_1, …, a_n-1, e-1)| = |F(K_a_1, …, a_n-1, a_n)| - 1. Here…