Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let (G_n) and (H_n) converge to the same graph limit, and let (T_n) be a convergent sequence with each T_n a spanning tree of G_n. Do there exist spanning trees P_n of H_n converging to the same limit as (T_n)?
Let bbig mu be a partition. A finite subset C of bbig mathbb Z_>0timesbbig mathbb Z_>0 is a configuration; write bbig rho(C) and bbig gamma(C) for the partitions obtained by rearranging its row and column lengths in decreasing order. Call…
Let C_3 and C_4 denote cycle graphs of lengths three and four, respectively. Form a graph by gluing two copies of C_3 along single edges to a single copy of C_4, and suppose the two triangles are not attached to opposite sides of the…
Given a digraph D=(V,A), two (not necessarily disjoint) subsets S,T⊆ V and a connectivity requirement k, develop a strongly polynomial time combinatorial algorithm for finding a minimum cardinality arc-set whose addition makes D…
Let G be a graph. Its independence complex Ind(G) is the simplicial complex whose faces are the independent sets of G, and let β denote its total Betti number. For every induced subgraph H of G, consider β(Ind(H)). Kalai–Meshulam total…
Although this conjecture is still open, its special case restricted to cubic graphs was proved in 1997 by Robertson, Seymour, and Thomas [12]. Three-edge-coloring cubic graphs on surfaces of small Euler genus Bojan Mohar (joint work with…
Can the sequence of metric balls in an infinite Cayley graph form a family of expanders?
Let s_r(K_k) denote the minimum number of edges in an r-Ramsey-minimal graph for the clique K_k. Quadratic-degree bound conjecture. For all rgeqslant 2 and kgeqslant 2, there exist a constant C>0 and a constant-degree polynomial function f…
Let hatR(G) denote the size Ramsey number, the minimal number of edges m such that there is a graph H with m edges such that in any 2-colouring of the edges of H there is a monochromatic copy of G. Let F_1 and F_2 be the union of stars.…
What kind of metric spaces does a proper scaling constant \sigmap exist? What are examples of such spaces? Our answer to the first question is the notion of p-conductive homogeneity introduced in [4]. where ∇f is the derivative of f . This…
Let k and m be positive integers. A graph is k-connected when its connectivity number is at least k, and f(G) denotes the minimum degree of G. Fujita–Kawarabayashi conjecture. There is a least non-negative integer f_k(m) such that every…
Let G be a 1-well-covered graph, let alpha(G) be its independence number, let n=|V(G)|, and write I(G;x)=∑_k s_kx^k for its independence polynomial. Roller-Coaster Conjecture for 1-well-covered graphs. For every permutation sigma of the…
Let n be a positive integer, and let d be a degree. An open XOR-magic graph and a closed XOR-magic graph are graphs admitting, respectively, an open or closed XOR-magic labeling. The graphs below are required to have order 2^n. For each…
Directed paths in Eulerian digraphs Jacques Verstraete The following is a special case of a conjecture of Bollob'{a}s and Scott on weighted paths in directed graphs (see: A proof of a conjecture of Bondy concerning paths in weighted…
If M is an oriented matroid of rank r on n elements, must \operatorname{diam}(G^*(M))\le n-r+2?
A cubic 8-circulant nut graph is a cubic nut graph admitting an 8-circulant structure. Nonexistence conjecture for cubic 8-circulant nut graphs. There exists no cubic 8-circulant nut graph. This is the only unresolved case in the cubic…
Let P=(T;U,V) be a 3M-DAP, define r_v=2[s_t-(v-1)s_v] and b^*=2s_v/r_v, and set hat b=⌈2s_v/r_v⌉. A b-pair is a maximal inseparable (T,V)-pair with |B|=b and |A|=(v-1)b+1. Reduced-pair conjecture. If s_t>(v-1)s_v and b^*=2s_v/r_v is not an…
Let r,m∈N satisfy 2≤ r and 1≤ m. Let G be a finite simple graph with exactly rm vertices and minimum degree at least m(r-1). Prove that there exist m pairwise disjoint sets of vertices K_1,…,K_m such that each K_i is a clique of size r.
Let G(n,m) denote the class of graphs with n vertices and m edges. For r=1/k, let n be a multiple of k, and let CO^1/k_e(G) and CO^1/k^+_e(G(n,m)) denote the proportional edge connectivity of a graph and the maximum such value over G(n,m),…
It seems feasible that the answer to this question is affirmative for every finite group G. In the graph-theoretic formulation of these problems, which we will describe below, Gordon’s setting corresponds to the complete graph case (in…