Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For given maximum degree d and diameter k, what is the largest possible number of vertices in a graph?
Let G be a simple graph on vertex set V(G)=[n], let R=Bbbk[x_1,…,x_n], and let I(G^d) be the edge ideal of the d-th power of G, where d is a positive integer. The Castelnuovo–Mumford regularity is denoted by reg. Monotonicity conjecture.…
For each positive integer n, let N_n,n(t) be the polynomial defined by the preceding generating-function construction for the expected one-dimensional Earth Mover's Distance on C(s,n) × C(s,n). Unimodality and palindromicity conjecture.…
Let G be a graph. An independent set is a set of vertices containing no edge of G, and a cover of the vertex set is a family of such sets whose union is the vertex set. Strong minimality is the dual notion to strong maximality: a cover is…
conjecture. The third highlight of the workshop was presented by Aleksa Milojević and Istvan Tomon in two consecutive talks, which covered their joint work with Zhihan Jin and Shengtong Zhang on spectral graph theory and its applications…
Let x_1,…,x_n be Q-linearly independent complex numbers. Assume that for any ε>0, there exists a positive number H_0 such that, for any H≥ H_0 and n-tuple (h_1,…,h_n) of rational integers satisfying 0<max|h_1|,…,|h_n|≤ H, the inequality…
Let G and overlineG be complementary connected graphs with n vertices. Ma's conjecture. There exist constants C_1 and C_2 such that trc(G)+trc(overlineG)≤ C_1n+C_2, and this upper bound is tight. This asks for a tight linear…
Conjecture There exists an integer k such that every k-arc-strong digraph D with specified vertices u and v contains an out-branching rooted at u and an in-branching rooted at v which are arc-disjoint.
Let G be a connected graph. Jiang, Li and Zhang's conjecture. It always holds that tmc(G)>mc(G). The conjecture compares the total monochromatic connection number with the monochromatic connection number for connected graphs; its status is…
Let G=(V,E) be a triangle-free graph of average degree d, let Z_G(λ) denote its independence polynomial, and let W be the Lambert W-function, defined by W(x)e^W(x)=x. Parameterized occupancy-fraction conjecture. For every λ∈(0,1], λ…
For a positive integer n, let A be a non-empty bridge-addable set of graphs on 1,…,n: whenever a graph belongs to A, adding an edge between vertices in distinct connected components produces another graph in A. Let G be uniformly…
Let G_∞ be the infinite grid, and let δ_t,r(G_∞) denote the minimum density of a (t,r) broadcast. Revised broadcast-density conjecture. For all t>2, δ_t,3(G_∞)=δ_t-1,1(G_∞). This equality is presented as the paper's revised conjecture…
A blink is a plane graph whose edges are bipartitioned into black and gray edges; switching the colors gives -B, and B^* denotes the dual blink in the sphere. A blink is monochromatic 3-connected if it has the property that all its edges…
If every edge has imbalance ≥1, is the multiset of edge imbalances always graphic?
Conjecture Every planar graph is acyclically 5-choosable.
What is the complexity of the vertical decomposition of n surfaces in R^d, d ≥ 5?
Let f(s,n) be the largest integer such that every n-vertex graph whose every induced s-vertex subgraph has an independent set of size at least log n must itself have an independent set of size at least f(s,n). Estimate f((log n)^2,n) and…
Let h(n) be minimal such that every graph on n vertices where every set of 7 vertices contains a triangle (a copy of K_3) must contain a clique on at least h(n) vertices. Estimate h(n) - in particular, do there exist constants c_1,c_2>0…
A bicirculant is a regular graph admitting a semiregular automorphism with two vertex-orbits of equal size; a graph is hamiltonian if it contains a Hamilton cycle. Let K_2 denote the complete graph on two vertices, and let G(m,2) be the…
For a finite group G, let bdom? P^*(G) denote its proper power graph, and suppose that this graph is connected. Bounded diameter conjecture. There exists a constant c such that, for every finite group G with connected proper power graph,…