Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For l∈N, let an l-deck be the multiset of l-vertex induced subgraphs of a graph, and call a graph ℓ-reconstructible if it is determined by its (n-ℓ)-deck. Manvel's conjecture. For l∈N, there exists a threshold M_ℓ such that every graph…
Conjecture There exists a fixed constant c (probably c=1 suffices) so that every graft with minimum T-cut size at least k contains a T-join packing of size at least (2/3)k-c.
For a finite simple undirected graph G, the degeneracy of G is the least integer d such that every non-empty subgraph of G has a vertex of degree at most d. For a positive integer k, a proper k-colouring of G is a map γ : V(G) → 1,…,k with…
For positive integers I and J, let H(I,J) be the least n such that there are I disjoint Golomb rulers, each a J-subset of 1,2,…,n. Incremental bound conjecture. If I≥1 and J≥3, then H(I+1,J)≤ H(I,J)+J. The proposed inequality would give a…
Let G be a graph without isolated vertices. Call an induced subgraph of G odd if all of its degrees are odd, and let f(G) denote the maximum order of an odd induced subgraph of G. Odd induced subgraph conjecture. There exists a constant…
Study the distribution of group structures E(F_q) as elliptic curves E/F_q vary; in particular, determine the correct nonuniform law.
Problem Does every 3-connected cubic graph G satisfy γ(G) ≤ ⌈ |G|/3 ⌉?
For each of the three random labeled chip-firing protocols described in the source—uniformly choosing a legal firing move, uniformly choosing an unstable vertex and then a pair of chips there, or uniformly choosing a labeled stabilization…
Let G be a finite undirected graph on n vertices. A dominating set is a set of vertices such that every vertex is either in the set or adjacent to a vertex in the set. For 0≤ j≤ n, let d_j(G) be the number of dominating sets of G with…
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. The parameters q,r are integers subject to the displayed decompositions…
For a metric space X, let e(X) denote the supremum of the cardinalities of subsets S ⊆ X that are equilateral, i.e. such that there is a constant λ > 0 with dist(x,y) = λ for all distinct x, y ∈ S. For an integer d ≥ 1 and a real number p…
Let p be an odd prime, let K_2p be the complete graph on 2p circularly ordered vertices, and let L be a list of p positive integers less than p. A perfect matching F of K_2p is a set of p pairwise disjoint edges covering all vertices, and…
Let F^*_n be the fan with a handle whose spokes are all edges connected to the hub except the edge connected to the degree 1 vertex. For all even ngeqslant 4, consider F^*_n with any two of these spokes removed. Even fans with handles and…
For every infinite, connected, vertex-transitive, cubic graph G, let c_n(G,v) denote the number of self-avoiding walks of length n starting at a vertex v, and let the connective constant be μ(G):=limsup_n→∞ c_n(G,v)^1/n. Then μ(G)≥φ, where…
Let G=(S,T;E) be a bipartite graph, with weights w:E → [0,1]. A proper weighted edge colouring is a colouring of the edges such that at each vertex, the sum of weights of edges of the same colour is at most 1. A lower bound for the number…
Let A be a vertex and let v,w be A-generic words, meaning that their arc-configuration sets equal the set defining A. The conf-configuration invariance conjecture. h(v)=h(w). Equivalently, if Conf(v)=Conf(w), then h(v)=h(w). The paper…
Find a good characterization for undirected graphs having a strongly connected (more generally k-edge-connected) orientation so that the in-degree of every node is odd.
Let d≥ 1. For a finite graph G, let its diameter be the maximum distance between two vertices, let its connectivity be the minimum number of vertices whose removal disconnects the graph, and call G Class 0 when its pebbling number f(G)…
Let G be a bridgeless cubic graph. A perfect matching is a set of edges meeting every vertex exactly once, and an edge-cut is the set of edges joining a vertex subset to its complement. Máčajová–Škoviera conjecture. Every bridgeless cubic…
Let G=(V,E) be a connected graph with |V|=n, and let x be a vertex such that d(x)=Δ(G)=n-k for some k≥4. Alon et al.'s large-maximum-degree conjecture. If n≥ n_0(k) for some n_0(k), then G is antimagic. This conjecture extends known…