Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
How many Sudoku puzzles have exactly one solution?
Fix a planar graph G and k=8, is it true that the distance between any two proper k-colorings of G is at most O(n)?
Conjecture If G is a non-empty graph containing no induced odd cycle of length at least 5, then there is a 2-vertex colouring of G in which no maximum clique is monochromatic.
A signed graph is a graph whose edges are designated even or odd; a cycle is even when it contains an even number of odd edges. A graph is even cycle decomposable if its edge set can be partitioned into even cycles. The graph is Eulerian…
Let G=C_n_1∪…∪ C_n_m be a 2-regular graph, where each n_i≥ 3, and let a graph be prime when it admits a labeling by distinct integers from 1,2,…,|V(G)| such that adjacent vertices receive relatively prime labels. Tout–Dabboucy–Howalla…
A graph is P_5-free if it has no induced subgraph isomorphic to the path P_5. Faudree–Favaron–Li conjecture. Any P_5-free graph is irredundance perfect. Puech proved this consequence by showing that every graph containing neither P_6 nor a…
Let PS_n+1 be the Pitman–Stanley graph on n+1 vertices, and let F_PS_n+1(1,0,1,0,…,0) denote its flow polytope with the indicated net flow vector. Pitman–Stanley volume conjecture. For n≥ 2, vol F_PS_n+1(1,0,1,0,…,0)=2^n-1-n-2. The formula…
Let G be a graph. Write dom_g(G,A) and dom_g(G,B) for the domatic game numbers when Alice and Bob, respectively, move first. First-player difference conjecture. For all graphs G, |dom_g(G,A)-dom_g(G,B)|≤ 1. The conjecture proposes that…
For each integer m≥ 4, let f_m and h_m be the polynomials defined in the paper, and let the ULC inequality refer to the ultra-log-concavity inequality for their coefficients. Higher-degree ULC failure conjecture. Both f_m and h_m are not…
Open problem: The most significant open problem in the area of graph matching at large is to theoretically justify the success of a natural and commonly used convex relaxation. Impossibility Results for Planted Matching Problems Yihong Wu…
Remove the imaginary-hyperelliptic and p≠2 restrictions from the complexity bound stated in the slides.
A complete n-vertex simple topological graph is a drawing of the complete graph on n vertices in which vertices are points and edges are simple curves, with no edge passing through a nonincident vertex and with any two edges meeting at…
The Simonovits--Sos conjecture asserts that the largest triangle-intersecting families of graphs on a fixed n-vertex set are the families obtained by fixing a triangle and taking all graphs containing it. Sumner's Universal Tournament…
Let G be a global amoeba graph of order n and minimum degree 1. Let e(G) denote its number of edges, let ⌊ n^2/4⌋ be the floor of n^2/4, and let H_n be the graph defined in Example 2(c) of the source. Extremal global amoeba conjecture.…
Let f_k(n) be the maximum possible chromatic number of a graph with n vertices which contains no K_k. Is it true that, for k≥ 4, f_k(n) ≫ fracn^1-1/k-1(log n)^c_k for some constant c_k>0?
For fixed q, is N_q(g)=max_C#C(F_q) increasing as a function of the genus g?
Is there a sequence 1≤ d_1<d_2<… with density 1 such that all products ∏_u≤ i≤ vd_i are distinct?
Determine the spectral properties of the Laplacian on the graph defined by a Penrose tiling, or by another higher-dimensional model of a quasicrystal.
Let r≥2, s≥1 and n≥ r(s+1) be integers. If F⊆binom[n]r contains no s+1 pairwise disjoint members, must | F|≤maxbinomr(s+1)-1r,binom nr-binomn-sr? The two candidate extremal families are all r-sets inside an (r(s+1)-1)-set and all r-sets…
Let an infinite sequence be a sequence whose terms are drawn from the four-letter alphabet A,B,C,D. A sequence is nonrepetitive if it contains no contiguous block of the form XX for a nonempty finite word X, and palindrome-free if it…