The world's unsolved problems
993 open questions across 14 fields, gathered from Wikipedia. Pick one and start thinking.
Showing all 993 problems · surprise me
-
Chvátal's toughness conjecture, that there is a number t such that every t-tough graph is Hamiltonian
Read on Wikipedia → -
The cycle double cover conjecture
every bridgeless graph has a family of cycles that includes each edge twice
Read on Wikipedia → -
The Erdős–Gyárfás conjecture on cycles with power-of-two lengths in cubic graphs
Read on Wikipedia → -
The Erdős–Hajnal conjecture on large cliques or independent sets in graphs with a forbidden induced subgraph
Read on Wikipedia → -
The Grünbaum–Nash-Williams conjecture on whether every 4-vertex-connected toroidal graph has a Hamiltonian cycle.
Read on Wikipedia → -
The linear arboricity conjecture on decomposing graphs into disjoint unions of paths according to their maximum degree
Read on Wikipedia → -
The Lovász conjecture on Hamiltonian paths in symmetric graphs
Read on Wikipedia → -
The Oberwolfach problem on which 2-regular graphs have the property that a complete graph on the same number of vertices can be decomposed…
The Oberwolfach problem on which 2-regular graphs have the property that a complete graph on the same number of vertices can be decomposed into edge-disjoint copies of the given graph.
Read on Wikipedia → -
What is the largest possible pathwidth of an n-vertex cubic graph?
Read on Wikipedia → -
The reconstruction conjecture and new digraph reconstruction conjecture on whether a graph is uniquely determined by its vertex-deleted…
The reconstruction conjecture and new digraph reconstruction conjecture on whether a graph is uniquely determined by its vertex-deleted subgraphs.
Read on Wikipedia → -
The snake-in-the-box problem
what is the longest possible induced path in an n-dimensional hypercube graph?
Read on Wikipedia → -
Sumner's conjecture
does every (2n-2)-vertex tournament contain as a subgraph every n-vertex oriented tree?
Read on Wikipedia → -
Szymanski's conjecture
every permutation on the n-dimensional doubly-directed hypercube graph can be routed with edge-disjoint paths.
Read on Wikipedia → -
Tuza's conjecture
if the maximum number of disjoint triangles is \nu, can all triangles be hit by a set of at most 2\nu edges?
Read on Wikipedia → -
The unfriendly partition conjecture
Does every countable graph have an unfriendly partition into two parts?
Read on Wikipedia → -
Vizing's conjecture on the domination number of cartesian products of graphs
Read on Wikipedia → -
Walescki's theorem for hypergraphs
Do complete k-uniform hypergraphs admit Hamiltonian decompositions into tight cycles?
Read on Wikipedia → -
Zarankiewicz problem
how many edges can there be in a bipartite graph on a given number of vertices with no complete bipartite subgraphs of a given size?
Read on Wikipedia → -
Are there any graphs on n vertices whose representation requires more than floor(n/2) copies of each letter?
Read on Wikipedia → -
Characterise (non-)word-representable planar graphs
Read on Wikipedia → -
Characterise word-representable graphs in terms of (induced) forbidden subgraphs.
Read on Wikipedia → -
Characterise word-representable near-triangulations containing the complete graph K4 (such a characterisation is known for K4-free planar…
Characterise word-representable near-triangulations containing the complete graph K4 (such a characterisation is known for K4-free planar graphs)
Read on Wikipedia → -
Classify graphs with representation number 3, that is, graphs that can be represented using 3 copies of each letter, but cannot be…
Classify graphs with representation number 3, that is, graphs that can be represented using 3 copies of each letter, but cannot be represented using 2 copies of each letter
Read on Wikipedia → -
Is it true that out of all bipartite graphs, crown graphs require longest word-representants?
Read on Wikipedia → -
Is the line graph of a non-word-representable graph always non-word-representable?
Read on Wikipedia → -
Which (hard) problems on graphs can be translated to words representing them and solved on words (efficiently)?
Read on Wikipedia → -
Delta-conjecture (1978)
consider a complete graph (V; E_1, \dots, E_d) each edge of which is colored by one of d colors such that there exists a triangle \Delta colored in three pairwise distinct colors. Then, in each chromatic component (V, E_i), i = 1, \dots, d, one can choose...
Read on Wikipedia → -
The imbalance conjecture
If the imbalance for each edge of a graph is at least 1, is the multiset of all edge imbalances always graphic?
Read on Wikipedia → -
The implicit graph conjecture on the existence of implicit representations for slowly-growing hereditary families of graphs
Read on Wikipedia → -
Ryser's conjecture relating the maximum matching size and minimum transversal size in hypergraphs
Read on Wikipedia →
Data last refreshed 2026-10-20 03:01 UTC.