Conway’s thrackle conjecture
Can a planar thrackle have more edges than vertices?
Combinatorics
Within Combinatorics · Search all subjects
Gyárfás–Sumner conjecture
Does excluding any fixed induced tree control a graph’s coloring needs once its largest clique is bounded?
Barnette’s Hamiltonian conjecture
Does every cubic, bipartite, planar, 3-connected graph contain a cycle visiting every vertex exactly once?
Sidorenko’s conjecture
Do random graphs minimize the density of every fixed bipartite pattern among graphs of the same edge density?
Birkhoff billiard conjecture
Are ellipses the only smooth strictly convex planar billiards that are integrable near the boundary?
Meyniel’s conjecture
Can O(√n) pursuers catch a visible evader on every connected n-vertex graph?
Hypergraph dualization
Can a classical polynomial-time algorithm recognize all minimal hitting sets?
Erdős–Turán additive basis conjecture
Must an additive basis of nonnegative integers have arbitrarily many representations of some sums?
Ryser’s Latin square conjecture
Does every odd-order Latin square have a transversal?
Erdős–Lovász Tihany conjecture
Can a graph be split into two parts retaining prescribed coloring needs?
Total coloring conjecture
Can every finite simple graph color its vertices and edges together using at most two colors beyond its maximum degree?
Deterministic NC perfect matching
Can a deterministic parallel algorithm find a perfect matching in every general graph with polylogarithmic time and polynomially many processors?
Tuza’s triangle packing conjecture
Can all triangles in any finite simple graph be destroyed by removing at most twice its maximum number of edge-disjoint triangles?
Ryser’s hypergraph conjecture
Does every finite multipartite uniform hypergraph have a vertex cover at most r−1 times its largest matching?
List edge-coloring conjecture
Do separate allowed-color lists on edges always need no more colors than ordinary edge coloring?
Graham’s pebbling conjecture
Moving a pebble across an edge costs two pebbles. Is the worst-case supply needed on a product graph at most the product of the supplies needed on its two factors?
Gersho’s conjecture in three dimensions
For many representative points in a uniform three-dimensional region, is a body-centered cubic arrangement asymptotically best at minimizing squared distance to the nearest representative?
Kelvin problem
What periodic partition of three-dimensional space into equal-volume cells uses the least shared surface area?
Shannon capacity of the seven-cycle
Seven symbols sit around a circle, and neighboring symbols can be confused. How many messages can long strings of these symbols carry with absolutely no decoding mistakes?
Lovász Hamiltonian path conjecture
Does complete symmetry among a connected graph’s vertices guarantee a route visiting every vertex exactly once?
Chvátal’s toughness conjecture
Is there one fixed level of resistance to vertex removal that guarantees a round trip visiting every vertex exactly once?
Erdős distinct distances problem
Must every set of n distinct points in the plane determine at least a constant times n/√log n different distances?