Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a connected graph, let K_n,n denote a complete bipartite graph, and let Δ(G) and χ_ss'(G) denote the maximum degree and semistrong chromatic index of G, respectively. Semistrong index improvement conjecture. If G is distinct from…
Let G be a planar graph, and let mu(G) denote its Markov width. Planar graph Markov width conjecture. There is a universal constant C such that μ(G) ≤ C whenever G is planar. Even more strongly, one may take C=6. The conjecture is…
Let q be a positive integer, and let P be a path whose vertex set is partitioned into m subsets V_1,…,V_m, each of size at least q-1. A subset of vertices is q-stable if no two of its vertices are at distance less than q, with distance…
Let G=(V,E) be a semisimple graph with |V|≥4 that is locally completable in R^3. Let g be the dot-product measurement map in dimension 3, and let P⊂ R^3 be finite. Dot-product realisation conjecture. One has |f_g,G(P^V)|≫ |P|^|V|-1, and…
Let K be a simplicial complex on [m], let k be a commutative ring with unit, and define L_K:=FL_k(μ_1,…,μ_m)/([μ_i,μ_j]=0, ∀i,j∈K). Let N_K:=⟨it GPTW/⟩_Lie⊂ L_K be the Lie subalgebra generated by the Grbić–Panov–Theriault–Wu generators,…
All graphs are finite and simple. A graph G is perfect if every induced subgraph H of G satisfies χ(H)=ω(H), where χ(H) is its chromatic number and ω(H) its maximum clique size. A graph is H-free if it has no induced subgraph isomorphic to…
Let G be a graph with maximum degree Δ, and suppose that G has positive Lin-Lu-Yau Ricci curvature everywhere. The exponential curvature bound. There exists a positive constant C such that |V(G)|≤ C^Δ. Without the C_3-free condition, a…
Let Q_n be the n-dimensional hypercube graph (so that Q_n has 2^n vertices and n2^n-1 edges). Is it true that every subgraph of Q_n with ≥ (1/2+o(1))n2^n-1 many edges contains a C_4?
Let g and k be parameters of a (g,k)-reverse multiple and let its associated Young graph be the (g,k) Young graph. The 1089 graph is the Young graph isomorphic to the (10,4) and (10,9) Young graphs. 1089 graph conjecture. The (g,k) Young…
Let C_n be the cycle on an odd integer n, and let C_4square C_n denote their Cartesian product. For an Italian dominating function on a graph, assign each vertex a value in 0,1,2 so that every vertex assigned 0 has neighboring assigned…
Is Arnold's sequence (u_k)_k≥1 the f-transform of the quadruple (2,4,4,4)?
Can we find G_1, G_2, G_3,… where lim_i→ ∞ |Z(G_1)|/|G_i| = 0 and Z(G_i) ≥ n/log(n).
Let G) be a simple assembly graph with n rigid vertices, each of degree 4, and let F_k denote the kth Fibonacci number. A Hamiltonian set of polygonal paths is a Hamiltonian set as defined for such assembly graphs. Tangled-cord extremal…
Let a graph be well-covered when all its maximal independent sets have the same cardinality; a maximum independent set is an independent set of cardinality α(G). The recognition complexity claim. It is NP-complete to recognize well-covered…
Can every planar graph be drawn with integer edge lengths?
Conjecture Every infinite graph is a proper minor of itself.
If G is a finite bipartite graph with parts A and B, q is at least 3, and f is a uniformly random proper q-coloring, does the random set f^{-1}(0) intersection A have positive association?
The full Mon- day program concluded with an open problem session designed to spark productive discussions for the rest of the week. Later in the week, Tung Nguyen updated the participants on his results on the Erdős–Hajnal conjecture, a…
Let Z be the graph shown in Figure 6: a longer path X joins the relevant subgraphs, with vertices a,b,c,d labelled as in that figure. No-perfect-state-transfer conjecture. Perfect state transfer does not occur between a and b in Z. The…
Let D_4 be the graph class referenced in the paper, consisting of the relevant maximal triangle-free graphs satisfying property D_4. Finite forbidden-subgraph conjecture for D_4. There exists a finite family F of graphs such that D_4 is…