Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
conjecture. In the recent paper [1], Bucić, Pham, and the speaker proved that these three conjectures are in fact equivalent, extending several previous particular results in this direction by Fox, Nguyen, Scott and Seymour; Nguyen, Scott…
Any graph on n vertices can be decomposed into O(n) many edge-disjoint cycles and edges.
Let G be a subgraph of the Cartesian product G_1square…square G_m. Here, VC-dens^*(G) denotes the VC-density of G. VC-density conjecture. |E(G)|/|V(G)|≤ VC-dens^*(G). The conjecture strengthens the paper's density bounds for subgraphs of…
Let G be a triangle-free graph with minimum degree delta geq 2. Triangle-free zero-forcing conjecture. 2δ -2 ≤ Z(G). This is the g=4 specialization of the broader girth–minimum-degree conjecture and concerns improving the trivial…
Let G be an n-vertex graph. A bipartite cut is a cut whose induced subgraph on one side is bipartite. Bogdanov–Neustroeva–Sokolov–Volostnov–Russkin–Voronov conjecture. Any n-vertex graph with fewer than 3n-6 edges admits a bipartite cut,…
A 1977 conjecture of Erdős and Hajnal [5] predicts a very different behaviour in graphs with a forbidden induced subgraph; formally, their conjecture says that: Conjecture 1 (Erdős–Hajnal). This conjecture remains open despite a…
Let G be a finite group and let S⊂ G. The generalized orbital graph Γ_G/H,S has node set G/H and edge set generated by the pairs H,gH for g∈ S. When H=id, it is a Cayley graph. A cubic Cayley graph is a Cayley graph in which every node has…
Let (G_k) be a locally convergent sequence of bounded-degree graphs, each having separation profile of order at most the square root of the subgraph size. Must the local limit be recurrent?
Conjecture Every oriented graph with minimum outdegree k contains a directed path of length 2k.
Let G be a finite connected simple graph, and let K[G] denote its edge ring. A graded ring has a q-linear resolution when its minimal graded free resolution is q-linear, and assume q≥ 3. Edge-ring hypersurface conjecture. If K[G] has a…
Obtain improved bound for arithmetic regularity lemma for cyclic groups.
Let G be a finite, simple, undirected graph of order n, and call a vertex set a forest cut if it is a vertex cut whose induced subgraph is a forest. Forest-cut conjecture. If G has less than 3n-6 edges, then G has a forest cut. Maximal…
Let (Γ,g,G) be an abelian gain graph, where G is a torsion-free abelian group, possibly 2-divisible. Let Z_1(Γ) be the integral cycle group, and suppose it has a basis consisting of balanced circles with at most 3 edges. Three-edge…
Conjecture 6. 3 0. (Mader, 1985) For all k ∈ Z+, there exists r ∈ Z+ such that every r-out-regular digraph contains a subdivision of the transitive tournament on k vertices. Notes: This conjecture is known for k = 3 (where r = 2), and k =…
Let G and H be non-isomorphic graphs. We call H a twin of G if there are embeddings G→ H and H→ G, that is, injective maps V(G)→ V(H) and V(H)→ V(G) preserving adjacency. Tree alternative conjecture. A tree has either none or infinitely…
Let P_i denote the path graph with i vertices, and let square denote the Cartesian product of graphs. For i≤ j with i,j∈Z_>1, consider P_isquare P_j. A graph has the complete maximal identity property if its maximal stable configuration is…
For fixed k, does the first player have a winning strategy in the strong Ramsey game R(K_n,K_k) in a number of moves bounded independently of n as n\to\infty?
Is it consistent that for some infinite cardinal \theta there exists a (\theta,\theta+2)-coloring graph? What is the relationship between compactness of chromatic number and compactness of coloring number?
The k = 1 case of Theorem 1 immediately leads to the following corollary that solves an open problem stated in [1]. Taking H to be a loop in Corollary 3 immediately leads to the following corol- lary, which solves another open problem in…
Let N_T(m,n) denote the number of tromino tilings of an m× n rectangle. Consider an extended domino-deficient rectangle with minimal dimensions m× n', where n'>n. Complexity conjecture. The complexity of the number of tromino tilings…