Unsolved Problems

Every finite simple graph on at least 3 vertices is uniquely determined by its vertex-deleted subgraphs....

Every tree can be gracefully labeled: vertices can be assigned distinct labels from $\{0, 1, \ldots, |E|\}$ such that edge labels (absolute difference...

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...

Can every graph be totally colored with at most $\Delta + 2$ colors, where $\Delta$ is the maximum degree?...

Does there exist a graph where the dominating number equals the eternal dominating number and both are less than the clique covering number?...

If Alice has a winning strategy for the vertex coloring game with k colors, does she have one for k+1 colors?...

What is the maximum chromatic number of biplanar graphs?...

Does every thrackle have at most as many edges as vertices?...

What is the maximum pathwidth of an n-vertex cubic graph?...

What is the longest induced path in an n-dimensional hypercube graph?...

Are there graphs on n vertices requiring more than floor(n/2) copies of each letter for word-representation?...

Classify graphs with representation number exactly 3....

Among bipartite graphs, do crown graphs require the longest word-representants?...

If every edge has imbalance ≥1, is the multiset of edge imbalances always graphic?...

Is the bondage number of a graph always ≤ 3Δ/2, where Δ is the maximum degree?...