Unsolved Problems

Every graph with chromatic number $k$ has a $K_k$ minor (where $K_k$ is the complete graph on $k$ vertices)....

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

Every bridgeless graph has a cycle double cover: a collection of cycles that covers each edge exactly twice....

Develop high-dimensional mathematics to model and predict behavior in large-scale distributed networks....

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 every bridgeless graph have a collection of cycles covering each edge exactly twice?...

For any fixed graph $H$, do $H$-free graphs contain large cliques or independent sets?...

Does every finite connected vertex-transitive graph have a Hamiltonian path?...

What is the chromatic number of the plane with unit distance graph coloring?...

Can the sum of eigenvalues of the Laplacian matrix of a graph be bounded by the number of edges?...

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

Is the pebbling number of the Cartesian product of two graphs at least the product of their pebbling numbers?...

Is the cop number of a connected n-vertex graph $O(\sqrt{n})$?...

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

Does every k-regular graph on 2n vertices admit a 1-factorization when k ≥ n (or k ≥ n-1 for even n)?...

Does every complete graph on an even number of vertices admit a perfect 1-factorization?...

For k-degenerate graphs, can any (k+2)-coloring be transformed to any other in polynomial steps via single-vertex recolorings?...

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

Is every graph class defined by excluding one fixed tree as an induced subgraph χ-bounded?...

Does every bridgeless cubic graph have a cycle-continuous mapping to the Petersen graph?...

For every graph, does the list chromatic index equal the chromatic index?...

Is a graph with maximum degree Δ(G) ≥ n/3 in class 2 if and only if it has an overfull subgraph with the same maximum degree?...

Is the total chromatic number of every graph at most Δ + 2, where Δ is the maximum degree?...

Can the crossing number of a graph be lower-bounded by the crossing number of a complete graph with the same chromatic number?...

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

Do minor-closed graph families have $\ell_1$ embeddings with bounded distortion?...

Can every planar graph be drawn with integer edge lengths?...

Does every graph with a planar cover have a projective-plane embedding?...

What is the minimum crossing number of the complete bipartite graph $K_{m,n}$?...

Is the crossing number of the complete graph $K_n$ equal to the value given by Guy's formula?...

Do planar graphs have universal point sets of subquadratic size?...

Does there exist a conference graph for every number of vertices $v > 1$ where $v \equiv 1 \pmod{4}$ and v is an odd sum of two squares?...

Does there exist a strongly regular graph with parameters (99,14,1,2)?...

For given maximum degree d and diameter k, what is the largest possible number of vertices in a graph?...

Does a Moore graph with girth 5 and degree 57 exist?...

Does every cubic bipartite three-connected planar graph have a Hamiltonian cycle?...

Is there a constant t such that every t-tough graph is Hamiltonian?...

Does every bridgeless graph have a collection of cycles that covers each edge exactly twice?...

Does every graph with minimum degree 3 contain cycles of lengths that are powers of 2?...

Does every graph family defined by a forbidden induced subgraph have polynomial-sized cliques or independent sets?...

Can every graph with maximum degree Δ be decomposed into at most ⌈(Δ+1)/2⌉ linear forests?...

Does every finite connected vertex-transitive graph contain a Hamiltonian path?...

For which 2-regular graphs H can the complete graph be decomposed into edge-disjoint copies of H?...

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

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

Does every (2n-2)-vertex tournament contain every n-vertex oriented tree?...

Can the edges of any graph be covered by at most 2ν triangles, where ν is the maximum size of a triangle packing?...

Does every countable graph admit a partition where every vertex has at least as many neighbors outside its part as inside?...