Unsolved Problems

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

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

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

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

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})$?...

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

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

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

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

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

What is the maximum number of edges in a bipartite graph on (m,n) vertices with no complete bipartite subgraph $K_{s,t}$?...

For the Cartesian product of graphs $G \square H$, is the domination number at least $\gamma(G) \cdot \gamma(H)$?...

Do complete k-uniform hypergraphs admit Hamiltonian decompositions into tight cycles?...

Characterize which planar graphs are word-representable....

Characterize word-representable graphs in terms of forbidden induced subgraphs....

Characterize word-representable near-triangulations containing K₄....

Is the line graph of a non-word-representable graph always non-word-representable?...

Which hard graph problems can be efficiently solved by translating graphs to their word representations?...

Do slowly-growing hereditary graph families admit implicit representations?...

For r-partite r-uniform hypergraphs, is the vertex cover number at most (r-1) times the matching number?...

Does every oriented graph have a vertex with at least as many vertices at distance 2 as at distance 1?...

Is the minimum dicut size equal to the maximum number of disjoint dijoins in a directed graph?...