Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a connected graph of order n. The path extremal conjecture. vcfc(G)≤ vcfc(P_n). Here vcfc(G) denotes the conflict-free vertex-connection number of G, and P_n is the path on n vertices. The conjecture proposes that among connected…
Let G be an n-vertex k-chromatic ℓ-connected graph, and let i_t(G) denote the number of independent sets of size t in G. Fixed-size independent-set conjecture. If k ≥ 4, k>ℓ, and t ≥ 3, then i_t(G) ≤ i_t(G^*). This proposes that the same…
Let n be a positive integer and let r_⋆ be the maximum value of the r-loading over triples of partitions of n. For a partition, notation such as (k^4) means four parts equal to k, and (2^2k) means 2k parts equal to 2. Maximizer conjecture…
An oriented colouring of an oriented graph is assignment c of colours to the vertices such that no two arcs receive ordered pairs of colours (c_1,c_2) and (c_2,c_1). It is equivalent to a homomorphism of the digraph onto some tournament of…
Let h(n) be minimal such that there is a graph on n vertices with n+h(n) edges which contains a cycle on k vertices, for all 3≤ k≤ n. Estimate h(n). In particular, is it true that h(n) ≥ log_2n+log_*n-O(1), where log_*n is the iterated…
Let G be a graph, and write c(G) for its cop number and cc(G) for its attacking cop number. Strong attacking-cop-number conjecture. For all integers k ≥ 4 there exists a graph H such that c(H)=k and cc(H)=2c(H). The conjecture asks whether…
Let G be a nonempty graph. For a vertex v and an edge e, write G-v and G-e for the graphs obtained by deleting v and e, respectively. The monotonicity sandwich conjecture. There exist a vertex v and an edge e such that…
Let Δ_i denote the graph associated with the i-dimensional subspaces of the finite polar space, and let κ_i, χ_i, and ξ_i be its corresponding graph parameters. For 0 ≤ i < n, let θ_i be any of κ_i, χ_i, or ξ_i. Distinctness conjecture. If…
Let L(2^n) be the Latin square of order 2^n, with n≥ 4, and let C be a critical set of minimal size in L(2^n). Writing S for this critical set, so that |S|=|C|, the minimal critical-set bound conjecture. 121· 4^n-4≤ |S|≤ 5^n-1. These…
Let G be the Grigorchuk group. The Grigorchuk non-amenability conjecture asserts that the product replacement graphs Γ_k( G) are non-amenable for all k≥ 5. This is a special case of the broader non-amenability conjecture and is stated as…
Conjecture If G is a cubic graph not containing a triangle, then it is possible to color the edges of G by five colors, so that the complement of every color class is a bipartite graph.
Let V'(x)=#φ(m) : 1≤ m≤ x and V(x)=#φ(m) ≤ x : 1≤ m. Does lim V(x)/V'(x) exist? Is it >1?
Let T_n,k denote the triangular grid obtained after k transformations from the n-grid, and let T_n,n-s^s denote an s-subgrid of T_n,n-s. For an edge, its edge value is the corresponding resistance label, and Interior(T_n,n-s^s) denotes the…
Let G be a cubic graph. For each possible combination of k 1-factors of G, let μ_k(G) be the minimum number of edges not contained in their union. A hypohamiltonian snark is a snark whose vertex-deleted subgraphs are Hamiltonian. Steffen's…
A cubic graph is a graph in which every vertex has degree 3. A graph is cyclically 4-edge connected if no edge cut of fewer than four edges separates two subgraphs each containing a cycle. A Kotzig graph is a cubic graph admitting a proper…
Arrange the entries in each layer of the Gr_2-simplex as coefficients of a polynomial in a,b,c according to the arrangement described in the paper. Divisibility conjecture. Each such polynomial is divisible by a+2b+c. This reformulates the…
Let f(n,d,k) be the minimum number of hyperplanes, counted with multiplicity, needed to cover every point of the d-dimensional triangular grid T_d(n) at least k times. Saying that the function is linear in n means that its dependence on n…
Let N_k,ℓ denote the number of labeled chips starting at the root of a k-ary tree in the setting of the paper, and let a stable configuration be one obtained from these chips by chip-firing. For a vertex v, let its children be ordered from…
Let M=(g(x),f(x)) be a Riordan array, and let P^(n)_M denote its n-th production matrix, defined by P^(n)_M=|^(n-1)M^-1overlineM^(n). Let M^(n) be the matrix produced by P^(n)_M. Higher production matrix conjecture. For every positive…
Is the list chromatic number χ_L(G)=o(n) for almost every graph G on n vertices?