Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Conjecture For every ε > 0 and every positive integer k, there exists r_0 = r_0(ε,k) so that every simple r-regular graph G with r ≥ r_0 has a k-regular subgraph H with |V(H)| ≥ (1- ε) |V(G)|.
Let G) be a connected, infinite, locally finite graph. For vertices u,v,w forming a path uwv with uv∉ E(G), write N(x) for the neighborhood of x and d_G(x) for its degree. Diestel's conjecture. The graph G has a Hamilton circle if…
Are there infinitely many Diophantine triples that are also D(n)-triples for three distinct integers n≠1?
Let G be a simple graph, let p_G(k) denote its chromatic polynomial, and let overlineG denote its complement. Suppose that p_G(k)=p_overlineG(k). Xu–Liu conjecture. Then G and overlineG have the same degree sequence. This conjecture…
A hull configuration is a point configuration lying either on a line segment or on the boundary of a convex polygon; a blank side is an edge of the convex hull containing only two points of the configuration. Let P be a hull configuration,…
Let G be a 2-connected non-planar graph contained in a closed surface F. For a pair (F,G), define its representativity by r(F,G)=min_C∈ C_F|C∩ G|, where C_F is the set of all essential loops embedded in F. Define r(G)=max_F∈Fr(F,G), where…
Update Joux's 2002 work by developing a systematic taxonomy of pairing-related computational assumptions.
Let P_n be the permutohedron with vertex set contained in the hyperplane H_0colon ∑_i=1^n x_i=n+1choose 2. Let H_1,…,H_m be affine hyperplanes different from H_0 whose union contains the vertex set of P_n. Hyperplane covering conjecture.…
If a graph G has girth greater than 4, can its edges always be oriented so that the orientation contains no directed cycle and no cycle becomes directed after reversing the orientation of a single edge?
Let M_g denote the maximum order of an extendable finite group action on a minimal graph of genus g. Assume that g is neither a square number nor one of the finitely many values listed in the preceding table. If g is prime, then…
Let G be a connected graph of order n, and let RE(G) denote its Randić energy. A sun and a balanced double sun are the graphs described in Figure 2 of Gutman, Furtula and Bozkurt (2014). Sun and balanced double sun conjecture. The…
There exist real numbers ε, α and β with 0<ε<1/2, α≥ 1 and β≥ 0, and a positive integer B, such that for any nonzero rational numbers x, y satisfying xy^Bnot=1, the following is true: if S denotes the set of prime numbers for which…
Let G be a connected graph on n vertices, and let b(G) denote the minimum number of rounds needed to burn all vertices of G. Burning Number Conjecture. b(G) ≤ ⌈√n⌉. This conjecture proposes a sharp upper bound for graph burning, improving…
Let b_t,i(n) denote the number of hooks of length i in all t-regular partitions of n. Singh–Barman's conjecture. For all n≥ 28, b_3,2(n)≥ b_3,1(n). This conjecture concerns the bias between hooks of lengths two and one in 3-regular…
Let w=(α_1,…,α_2n) be a conf-connected word, let a be its minimal letter, and let I_w(a) denote the positions occupied by a. Set i=max(I_w(a)), j=max(I_w(a+2)). Let mathringw_(i,j) be the word obtained by deleting the letters in positions…
Suppose Z acts on a graph G by isometries, the quotient H=G/Z is Liouville, and simple random walk on G visits every translate of a fundamental domain infinitely often almost surely. Must G be Liouville?
Let G be a simple connected graph. Write D(G) for its distinguishing number and st_D(G) for its distinguishing stability, namely the least number of vertices whose deletion changes the distinguishing number. Distinguishing stability…
Let n≥ 5 be an integer, and let G be an n-vertex graph. Write overlineG for its complement and let η(G) denote the number of connected induced subgraphs of G. Diameter-two conjecture. If η(G)+η(overlineG)≥ η(H)+η(overlineH) for every graph…
Let k and n_1,n_2,…,n_k be positive integers, and let d be the degree. Consider the zero weight space in degree d for the n_1×…× n_k array representation. Polynomiality conjecture. Its dimension is given by a family of polynomials in d of…
Let G be a connected graph other than K_1,n and K_3. Write b(G) for its bondage number, δ(G) for its minimum degree, and λ'(G) for its restricted edge-connectivity. Bondage–edge-connectivity conjecture. b(G)leqslantδ(G)+λ'(G)-1. The source…