Graphs and coloring
Colors, subgraphs, labels and paths that visit every vertex.
20 problemsGraph theory
Networks of vertices and edges.
Collections
Browse collectionsGames and strategies
Perfect play in chess, winners in graph games, and pursuit strategies.
3 problemsA few problems to explore
26 totalHadwiger conjecture
A graph that needs many colors is predicted to contain a correspondingly large complete graph after edges are contracted and vertices removed.
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?