Unsolved Problems
Showing 1-20 of 20 problems
Reconstruction Conjecture
Every finite simple graph on at least 3 vertices is uniquely determined by its vertex-deleted subgraphs....
The Graceful Tree Conjecture
Every tree can be gracefully labeled: vertices can be assigned distinct labels from $\{0, 1, \ldots, |E|\}$ such that edge labels (absolute difference...
Cereceda's Conjecture
For any $k$-chromatic graph, can its $k$-colorings be transformed into each other by recoloring one vertex at a time, staying within $k$ colors, in po...
The Total Coloring Conjecture
Can every graph be totally colored with at most $\Delta + 2$ colors, where $\Delta$ is the maximum degree?...
Eternal Domination vs Domination Number
Does there exist a graph where the dominating number equals the eternal dominating number and both are less than the clique covering number?...
Graph Coloring Game Monotonicity
If Alice has a winning strategy for the vertex coloring game with k colors, does she have one for k+1 colors?...
Earth-Moon Problem
What is the maximum chromatic number of biplanar graphs?...
Conway's Thrackle Conjecture
Does every thrackle have at most as many edges as vertices?...
Cubic Graph Pathwidth
What is the maximum pathwidth of an n-vertex cubic graph?...
Snake-in-the-Box Problem
What is the longest induced path in an n-dimensional hypercube graph?...
Word-Representable Graphs: Letter Copies Bound
Are there graphs on n vertices requiring more than floor(n/2) copies of each letter for word-representation?...
Representation Number 3 Classification
Classify graphs with representation number exactly 3....
Crown Graphs and Longest Word-Representants
Among bipartite graphs, do crown graphs require the longest word-representants?...
Imbalance Conjecture
If every edge has imbalance ≥1, is the multiset of edge imbalances always graphic?...
Teschner's Bondage Number Conjecture
Is the bondage number of a graph always ≤ 3Δ/2, where Δ is the maximum degree?...
Reconstruction conjecture
The deck of a graph $G$ is the multiset consisting of all unlabelled subgraphs obtained from $G$ by deleting a vertex in all possible ways (counted ac...
Cycle double cover conjecture
Conjecture For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two....
The Berge-Fulkerson conjecture
Conjecture If $G$ is a bridgeless cubic graph, then there exist 6 perfect matchings $M_1,\ldots,M_6$ of $G$ with the property that every edge of $G$ i...
5-flow conjecture
Conjecture Every bridgeless graph has a nowhere-zero 5-flow....
Caccetta-Häggkvist Conjecture
Conjecture Every simple digraph of order $n$ with minimum outdegree at least $r$ has a cycle with length at most $\lceil n/r\rceil$...