Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a graph, and let the chromatic number of G be its minimum number of colors in a proper vertex coloring. An induced cycle is a cycle whose vertices induce exactly the edges of the cycle. Kalai–Meshulam chromatic conjecture. A graph…
Show that BP fails on the SBM below the KS bound.
Let k ≥ 3 be an integer. A k-clique isolating set of a graph is a vertex set whose closed neighborhood leaves no copy of K_k. The partition conjecture. Every connected graph, except K_k, can be partitioned into k+1 disjoint k-clique…
Let m≥ n≥ 1 be integers, and let a denote the additional width parameter in a tree-decomposition of the (n× m)-grid whose width is n+a. The spread versus width conjecture. There is a constant δ>0 such that every such tree-decomposition has…
For a graph G and finite vertex sets T,Y, say that Y is joined to two vertices of T if every y∈ Y is adjacent to two distinct vertices u,v∈ T. Is it true that, for every ε>0, all sufficiently large n, and every graph G on n vertices with…
Every d-regular graph has an edge signing whose signed adjacency matrix has spectral radius at most 2 times the square root of d-1.
Let G be a graph in C and let v∈ V(G) be such that G-v∈C. Vertex-deletion conjecture. rm DOM_t(G)≤ rm DOM_t(G-v)+1. The conjecture proposes the missing lower bound from the cited vertex-deletion result; the corresponding upper bound for…
Let P_k^irr be the set of all irreducible polyhedral graphs with k rigid vertices. Finiteness conjecture. Each set P_k^irr is finite. This conjecture asserts that, unlike reducible polyhedra, irreducible polyhedral graphs cannot have an…
What precise notions of negative curvature imply congestion?
Erdős-Gyárfás: Is it true that every graph whose vertices have odd degree greater than one contains a cycle of length 2^(n) for some n? This one has kept me (and apparently, lots of others) up many a night trying fruitlessly to construct a…
Let G be a finite graph with no pendant edges. Let a line be a metric line in G, and let a bridge be an edge whose deletion disconnects G. AMRZ line-and-bridge conjecture. In all graphs with no pendant edges, except for finitely many…
Given a prime p and f∈(Z/pZ)[x] known to have a root, can a root be found in deterministic polynomial time?
Let P be a finite set in R^2, and let G=(V,E) be a finite, simple, connected graph. Write f_G(P^V) for the set of Euclidean distance measurements on the edges of G arising from maps of V into P. Graphical distinct-realisation conjecture.…
Let Shuf(m,n) be the shuffle lattice, and let M_m,n(q,t) denote its M-triangle. For integers m,n≥ 0, the explicit M-triangle conjecture. M_m,n(q,t)=∑_a≥ 0binommabinomnat^a(1-t)^a(q-1)^a(qt-t+1)^m+n-2a. This formula is conjectured in view…
Problem 4.13 (Brought by V. Lev, originally stated by Konyagin and the presenter). Suppose we are given r ≥ 1 points z1,..., z r on the unit circle and corresponding non-negative weights p1,..., p r, normalized by the condition p1 + · · ·…
Let G be a 2-edge-connected graph, let vecG be an orientation of G, and let tac(vecG) denote its total arc-connectivity. An orientation maximizes total arc-connectivity when it maximizes tac(vecG) among all orientations of G. An…
Label the faces of a unit cube with numbers 1--6 as in a die. Place the cube to sit on an integer lattice grid, with one corner at the origin and sides aligned with the axes. Completely label every lattice square of a rectangular ``board''…
For positive integers d and n, let S_d,n denote the set of d-dimensional permutations of order n: equivalently, the [n]^d arrays with entries in [n] in which every line contains each element of [n] exactly once. Thus |S_d,n| is the number…
Let G=(V,E) be an undirected graph and let (s_1,t_1), (s_2,t_2) be two node pairs. Give a combinatorial, polynomial-time algorithm to find edge-disjoint s_1-t_1 and s_2-t_2 paths with minimum total length.
Conjecture 6. 1 9. (Bermond-Thomassen) In a digraph D with δ+ D ≥ 2k − 1, there are k vertex disjoint cycles. Notes: Open for k ≥ 3, and the proof for k = 2 by Thomassen is not intuitive.