Hadwiger conjecture
A graph that needs many colors is predicted to contain a correspondingly large complete graph after edges are contracted and vertices removed.
Graph theory
Within Graph theory · Search all subjects
Hadwiger–Nelson problem
How many colors are needed to color every point of the plane so that points exactly one unit apart always have different colors?
Erdős–Hajnal conjecture
Forbidding one fixed induced graph is predicted to force a large group of vertices that are all connected to each other or all disconnected.
Graceful tree conjecture
Every tree is predicted to admit vertex numbers whose differences across edges are all distinct and fill the required range.
Caccetta–Häggkvist conjecture
If every vertex of a directed graph points to many others, must the graph contain a correspondingly short directed cycle?
Graph reconstruction conjecture
Delete each vertex of a graph in turn and keep the resulting graphs without labels. Does this collection determine the original graph?
Tutte’s five-flow conjecture
Can every graph without a bridge carry a balanced flow that never vanishes and uses only four positive magnitudes?
Erdős–Gallai cycle decomposition conjecture
Can the edges of any graph be split into only a constant times its number of vertices worth of cycles and individual edges?
Seymour’s second-neighborhood conjecture
Must a directed graph without two-way edges have a vertex reaching at least as many new vertices in two steps as in one?
Small-Set Expansion hypothesis
Is it computationally hard to distinguish a graph with a small nearly isolated set from one where every equally small set strongly expands?
Densest-k-subgraph approximation
Can a fast algorithm always choose k vertices spanning within a fixed factor of the largest possible number of edges?
Conway’s thrackle conjecture
Can a planar thrackle have more edges than vertices?
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?
Meyniel’s conjecture
Can O(√n) pursuers catch a visible evader on every connected n-vertex graph?
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?
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?