Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let C_n be the cycle graph on n vertices, let K_1 be the one-vertex graph, and let C_n⊙ K_1 denote their corona product. A graph is determined by its (signless) Laplacian permanental polynomials if no non-isomorphic graph has the same…
For every finite poset P with n=|P|, determine the facet-count gap gap(P):=f_n-1(C(P))-f_n-1(O(P)), where O(P) and C(P) are respectively the order and chain polytopes of P. In particular, seek a structural determination, classification,…
Let G be a rich flow admissible graph with maximum degree Δ. A pair of edges is confluent when the relevant flow values coincide in the sense used by the paper; a nowhere-zero k-flow is a Z-flow with nonzero edge values of absolute value…
For connected alternating-current networks with b boundary vertices and complex response matrix \Lambda, give an algorithm to reconstruct a network and positive-real edge conductances from \Lambda; describe the response sets of…
Let P_n(x) denote the row sum polynomials of the matrix generated by regarding overlineA as a production matrix. The initial polynomials are 1, 2-x, x^2-3x+3, -x^3+5x^2-8x+5, x^4-8x^3+22x^2-25x+11,…. Row sum polynomial conjecture. For…
Let P_3,n be the set of (3,n)-parking functions, let pides(π)=2^a1^b, let Φ be the involution whose fixed points are the fixed parking functions, and let S be the switch map. The switch-map conjecture. For any π∈P_3,n with pides(π)=2^a1^b,…
Does there exist an integer ell such that every cubic graph of girth at least ell admits a graph homomorphism to the cycle C_5?
For a full-rank integer lattice, is finding a nonzero vector of minimum Euclidean norm NP-hard?
Let G be a graph, let S be the polynomial ring associated with G, and let J_G be its binomial edge ideal. Assume that p=2. Weak-closedness characterization. The quotient S/J_G is F-pure if and only if G is weakly closed. The preceding…
For a graph G, let b1(G) denote its independence number, and let c(G) denote the minimum number of cops needed to capture a robber on G. Turcotte's conjecture. For any positive integer p and any graph G such that α(G)<p, we have c(G)≤ p-2.…
For all sufficiently large n, every coloring C:binomFin(n)2→0,1 of the edges of the complete graph on Fin(n) has at most n^2/4 edges that do not lie in a monochromatic triangle. Equivalently, the set of unordered non-diagonal pairs e such…
Let d_ℓ(m) be the sequence described above, and define the operator L(x_k)=x_k^2-x_k-1x_k+1. A sequence is infinitely logconcave if L^j(x_k) is nonnegative for every j∈N. Infinite logconcavity conjecture. The sequence d_ℓ(m) is infinitely…
Is there some function f such that for all k≥ 3 if a finite graph G has chromatic number ≥ f(k) then G must contain some odd cycle whose vertices span a graph of chromatic number ≥ k? ", "difficulty": "L1" },{
Conjecture Is there a graph G that is a minor-minimal obstruction for two non-orientable surfaces?
Let G be a simple graph. Write c(G) for its number of components, and define its toughness by τ(G)=min|S|/c(G-S):S⊆ V(G), c(G-S)≥ 2 when G is not complete, with τ(G)=∞ otherwise. The graph is t-tough if τ(G)≥ t. Let d_1≤ d_2≤…≤ d_n be the…
Let k∈N, and let G be a graph. For a vertex x∈ V(G), let N(x) denote its neighbourhood and let N_2(x) denote its second neighbourhood. Large first- and second-neighbourhood conjecture. If δ(G)≥ k/2 and there is a vertex x such that…
Let G be a connected graph. Write R_α=1(G) for the Kirchhoff index based on the hubs-repelling resistance distance, R_α=0(G) for the standard Kirchhoff index, and R_α=-1(G) for the Kirchhoff index based on the hubs-attracting resistance…
Given a string x ∈ 0, 1^n, let tildex be obtained by deleting bits independently at random with probability 1/2. How many independent traces tildex_1, …, tildex_m are needed to reconstruct x with probability 0.9?
Let a knot diagram determine its universe, and let the associated balanced overlaid Tait graph have a number of cycles. Let the bridge number be the minimum number of bridges among diagrams of the represented knot. Cycles–bridge-number…
Question Let G be an (a+b+2)-edge-connected graph. Does there exist a partition A,B of E(G) so that (V,A) is a-edge-connected and (V,B) is b-edge-connected?