Unsolved Problems

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

If a polynomial of degree d over a field of characteristic 0 shares a factor with each of its first d-1 derivatives, must it be $(x-a)^d$?...

Is $\|f(A)\| \leq 2 \sup_{z \in W(A)} |f(z)|$ for any matrix A and analytic function f on the numerical range W(A)?...

Characterize the determinant of the sum of two normal matrices....

Does every group with cohomological dimension 2 have a 2-dimensional Eilenberg-MacLane space K(G,1)?...

Is every finite lattice isomorphic to the congruence lattice of some finite algebra?...

Does a Hadamard matrix of order 4k exist for every positive integer k?...

If a ring has no nil two-sided ideal besides {0}, does it also have no nil one-sided ideal besides {0}?...

Given n bases of an n-dimensional matroid, can we find n disjoint rainbow bases?...

Can all regular languages be expressed with generalized regular expressions having bounded star height?...

Do Henson graphs have the finite model property?...

Is every infinite minimal field of characteristic zero algebraically closed?...

Are Berge knots the only knots in S³ admitting lens space surgeries?...

Can unknots be recognized in polynomial time?...

Is every connected subcomplex of a 2-dimensional aspherical CW complex also aspherical?...