Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Determine how the bound 2a(G)\geq n(G)-m(G) for C_3- and C_4-free graphs of maximum degree at most 3 extends to larger girth or unrestricted maximum degree, and determine the extremal graphs.
Let T be a tree with ℓ leaves, and let DT be the set of all directed rooted trees, namely trees with a distinguished root and all edges oriented away from it. Write vecD(T,DT) for the oriented discrepancy of this family in T. Asymptotic…
In graph-construction games with highly irregular target graphs, can Maker use a global strategy that postpones deciding which board vertex represents which vertex of the target G, and thereby obtain an asymptotically faster construction…
Let N be the number of vertices of the quiver, let X_t be the indexed set of lattice points used to construct calibrated representations, and let M(S,t) denote the representation associated with a finite poset S⊆ X_t; write M(z) for the…
Let n, k, and k^′ be integers with n≥ k≥3 and k>k^′≥1, and let T be a tree with order n. The Steiner diameter–radius conjecture. Sd_k(T)≤frackk-k^′Sr_k,k^′(T)-frack^′(k^′-1)k-k^′. The paper proves the inequality for k^′=2 and k^′=3, and…
Let q_1,…,q_n be nonzero algebraic numbers in the unit open disc such that the 3n numbers J(q_i), DJ(q_i), D^2J(q_i) (i=1,…,n) are algebraically dependent over Q. Then there exist two indices inot = j \ (1≤ i≤ n, 1≤ j≤ n) such that q_i and…
Let G be a cubic graph. A frame of G is a spanning subgraph H such that the contraction G/H is even. For a subgraph H, let overlineH denote the graph obtained by suppressing all degree-2 vertices. A semi-Kotzig frame is a frame whose every…
Given a prime p, can a generator of (Z/pZ)^* be found in deterministic polynomial time?
Let G be a triangle-free planar graph. An induced subgraph is 2-degenerate if every nonempty subgraph of it has a vertex of degree at most 2. Seven-eighths conjecture. Every triangle-free planar graph contains an induced 2-degenerate…
Any graph on n vertices can be decomposed into O(n) many edge-disjoint cycles and edges.
Let G be a bridgeless graph, and let C be a cycle in G. A cycle double cover is a list of cycles in G in which each edge appears exactly twice. Goddyn's conjecture. There exists a cycle double cover of G containing C. The paper says its…
Let G be a graph of sufficiently large order. For an integer t≥ 1, let σ_t(G) denote the minimum degree sum over all sets of t pairwise nonadjacent vertices of G. Gould–Hirohata–Keller conjecture. If σ_t(G)≥ 2kt-t+1 for any two integers k≥…
Let f(z) be an entire function which is not a monomial. Let u(r) count the number of z with lvert zrvert=r such that lvert f(z)rvert=max_lvert zrvert=rlvert f(z)rvert. (This is a finite quantity if f is not a monomial.) Is it possible for…
Let n and ℓ be integers satisfying n≥ ℓ≥ 1. Let totalD(n,k) denote the total quantity studied in the paper, and let totalDTrunc(n,k) denote its truncated version. For each ℓ, let a_ℓ(n) and b_ℓ(n) be polynomials in n. Polynomial-formula…
A cograph minimal (∞,k)-polar obstruction is a cograph that is not (∞,k)-polar but whose every proper induced subgraph is (∞,k)-polar; its type (c,i) records its number c of connected components and its number i of isolated vertices. For…
Let G be a bridgeless cubic graph, and let M_1,M_2 be 1-factors of G. Acyclic two-matchings conjecture. There exist two 1-factors such that the complement of their union is acyclic. The paper identifies this as a stronger version of the…
Let G be the collection of all connected graphs of order at least 3 with at most two blocks. A graph is 2-bootstrap good if it contains at least one pair of vertices that percolate under the r=2 bootstrap percolation process. A graph is…
Let mathcal G be a finite abelian group, let D(mathcal G) denote its Davenport constant, and let G be a graph. A graph is zero-forcing for mathcal G if every mathcal G-labeling of its vertices has a non-empty connected zero-sum subgraph.…
Let G be a planar graph of order n. The graphical Stirling numbers of the first kind are the numbers stGk for 1≤ k≤ n. A sequence is unimodal if there exists an index k_0 such that stG1 ≤ … ≤ stGk_0 ≥ … ≥ stGn. Planar-graph unimodality…
Let n and k be natural numbers with n≥ 2k+1. The vertex set of the Kneser graph K(n,k) is binom[n]k, with two vertices adjacent exactly when they are disjoint. For a connected graph G, define its toughness by t(G)=min_S|S|/c(G∖ S), where…