Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a maximal 3-γ_c-vertex critical graph, and let α, κ, and δ denote its independence number, connectivity, and minimum degree, respectively. Assume α=κ=δ. Hamiltonian connectivity conjecture. Then G is either the 5-cycle C_5 or…
For integers k≥ n≥3, other than k=n=3, is R(C_k,K_n)=(k-1)(n-1)+1?
For each base b≥ 3, define the successor graph G_s to have one node for every positive integer and a directed edge from i to j when j is the successor to i. A path has infinite length if it contains infinitely many edges. Successor-graph…
Let D^odd_k,n and D^even_k,n denote the odd- and even-parity D(k) graphs constructed in the paper, with order parameter n. Minimum-order conjecture. For all k≥ 3, there exists no D^odd_k,n for all n < 4k-3 and D^even_k,n for all n < 3k.…
Does every planar triangle-free graph with maximum degree at most 3 have fractional chromatic number at most 8/3?
The first rigorous solid standard Young tableaux challenge asks for a proof of a conjectured second-order recurrence for the number of solid standard Young tableaux. The conjectured recurrence is proved.
Let G be a graph, let I(G;x) denote its independence polynomial, and let φ(G) denote its decycling number. For a positive integer k and an integer q, consider the values of I(G;-1) for graphs whose decycling number is k. Realizability…
Let G be a connected graph. For c,k∈N, a c-quasi-geodesic (geqslant ck)-subdivision of K^3 means a subdivision of the triangle whose subdivided paths are c-quasi-geodesic and have length at least ck. The radial tree-width of G is the…
For a finite simplicial complex Δ of dimension d let f_i = f_i(Δ) denote the number of i-dimensional faces of Δ for 0 ≤ i ≤ d, with the convention f_-1 = 1, and call f(Δ) = (f_0, f_1, …, f_d) the f-vector of Δ. Define the h-vector (h_0,…
Let G be a connected graph. Write reg(G) for the minimum number of edge-partition classes whose induced subgraphs are regular, and let Δ(G) be the maximum degree of G. The degree-bound conjecture. For every connected graph G, reg(G)≤ Δ(G).…
Let n,k be two integers such that 1≤ k≤ n-2 and n is even. Let G be a graph on n vertices. A graph is of Ore-type-(k-2) if every pair of nonadjacent vertices u,v satisfies d(u)+d(v)≥ |G|+k-2. Win's conjecture. If G is of Ore-type-(k-2),…
Let bmathbbG_t and bmathbbG'_t be graphs non-decreasing in t, of uniformly bounded degrees, with bmathbbG_t⊆bmathbbG'_t for every t. Let bmathbbY_t and bmathbbY'_t be simple random walks on these graph evolutions, both starting from y_0.…
Let G be a connected graph with maximum degree 3, let K_3,3 be the complete bipartite graph, let the 5-prism be the graph named in the source, and let χ_ss'(G) denote the semistrong chromatic index of G. Subcubic semistrong index…
Let G_k have vertices x,y_1,…,y_k and z_ij for 1≤i<j≤k, with edges xy_i, z_ijy_i, and z_ijy_j. Is the maximum number of edges in an n-vertex graph containing no copy of G_k at most c_k n^3/2?
Does every graph with a planar cover have a projective-plane embedding?
Conjecture Every 4k-edge-connected graph can be oriented so that indegree(v) - outdegree(v) ≅ 0 (mod 2k+1 ) for every vertex v.
Consider either combinatorial nonadaptive group testing, where k uniformly randomly chosen items among n are defective, or probabilistic nonadaptive group testing, where each of the n items is independently defective with probability…
Fix an integer d≥ 1. Let (d_1,…,d_r)vdash d range over strictly positive unordered partitions of d, and let #Aut(d_1,…,d_r) denote the order of the automorphism group of the partition. Combinatorial identity conjecture. Then…
Let G be a graph, and write c(G) for its cop number. The graph G is 2P_2-free if it has no induced subgraph consisting of two vertex-disjoint copies of the path on two vertices. Sivaraman–Testa's conjecture. If G is 2P_2-free, then c(G)≤…
Let BestStep denote the problem of computing an optimal next step for the online covering problem for the time-dependent biased random walk on a graph. BestStep hardness conjecture. For undirected graphs, BestStep is PSPACE-hard. The paper…