Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let α(k,r) be the parameter defined as the minimum number of edges between a specified independent transversal and its complement over all K_r-partite-saturated k-partite graphs, with k≥ r≥ 3. The conjecture for α(k,r). For 5≤ r≤ k≤ 2r-4,…
A binary tree is a tree in which every vertex has degree 1 or 3. A rooted binary tree is a rooted tree whose root has degree 2 and whose other vertices have degree 1 or 3. A rgood binary tree is a rooted greedy binary tree with root degree…
At least three of the four numbers π, Γ(1/5), Γ(2/5), e^π√ 5 are algebraically independent over Q.
Let G be a diameter-2 graph, let H⊆ G be a subgraph, and let c_G(H) denote the least number of ordinary cops needed to catch a robber restricted to H, while the cops may move along all edges of G. Call H an s-trap when the robber can be…
Let G be a Cohen--Macaulay very well--covered graph with 2n vertices, and let I(G)^∨ be its cover ideal. For each k≥ 0, let HS_k((I(G)^∨)^ℓ) be the kth homological shift ideal of the ℓth power, and order the variables lexicographically by…
all weight sequences normalized by the number of random walks, converge almost surely to some deterministic constants, and we conjecture that this is a general fact which should hold on any finite graph. Several problems on this model…
Let t_m denote the total number of rectangulations of a square with m tiles, and write n for a positive integer. Parity conjecture. t_n≡ 1 mod 2 if n=8k+1 or n=8k+4; otherwise, t_n≡ 0 mod 2. This conjecture is motivated by the computed…
Conjecture A total coloring of a graph G = (V,E) is an assignment of colors to the vertices and the edges of G such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive…
A nowhere-zero r-flow (D(G),φ) on G is an orientation D of G together with a function φ from the edge set of G into the real numbers such that 1 ≤ |φ(e)| ≤ r-1, for all e ∈ E(G), and ∑_e ∈ E^+(v)φ(e) = ∑_e ∈ E^-(v)φ(e), for all v ∈ V(G).…
Let G be a simple graph with vertex set V(G)=v_1,…,v_n. Let Z^o_G be the scheme of nondegenerate symmetric n× n matrices M satisfying M_ij=0 if i≠ j and there is no edge from v_i to v_j. Equivalently, for a graph G^* obtained from G by…
Let Γ=(V,E) be a (d,ℓ)-tight multigraph, with ℓ<4d+2/3. Let K_2^2k-ℓ denote the graph with two vertices and 2k-ℓ parallel edges, and let a d-dimensional k-extension be the graph operation used in the conjecture. Szegö's conjecture. The…
Let G_k(n) denote the grid graph considered in the paper, with the recurrence for its spanning-tree counts taken with respect to n. Grid recurrence order conjecture. The recurrence for the grid graph G_k(n) has order 2^k-1. This predicts…
Is f pnq “ Opnq? Karim Adiprasito ř Question 12. Given a graph G and C a collection of cycles, let \C}1 “ \gammaPC |\gamma| be the total length. Given a field F and C, glue in the corresponding 2-disks into the cell complex underlying the…
Is recognition of primitive roots modulo a prime in randomized polynomial time R?
A graph G is k-degenerate if every subgraph of G has a vertex of degree ≤ k. Conjecture Every simple planar graph has a 5-coloring so that for 1 ≤ k ≤ 4, the union of any k color classes induces a (k-1)-degenerate graph.
Let C_n(1,3) be the circulant graph on vertex set Z_n in which vertices at cyclic distances 1 or 3 are adjacent. A locating-dominating code is a dominating vertex set whose vertices outside the code have distinct sets of codeword…
Does Thomassen’s conjecture extend to infinite graphs: does every infinite 4-connected line graph contain the corresponding Hamiltonian object, namely a Hamilton circle in the infinite-graph setting described in the report?
Let n≥ 2. Define m_1(n),m_2(n),m_3(n),m_4(n) to be the four largest possible numbers of valid color vectors, modulo the action of S_3 on the colors, among tree pairs corresponding to maps in W and having n internal vertices each, with…
Let G=(V,E) be a simple undirected graph with adjacency matrix A. For β>0, the β-subgraph centrality of vertex i is [e^β A]_ii, and G is walk-regular when [A^r]_ii=[A^r]_jj for all vertices i,j and every positive integer r.…
Let G be a connected d-regular graph, let t(G) denote its toughness, and let λ be the second largest absolute eigenvalue of the adjacency matrix of G. Brouwer's toughness conjecture. For any connected d-regular graph G, t(G)≥ d/λ-1.…