Unsolved Problems

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

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

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

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

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

Classify graphs with representation number exactly 3....

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

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

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

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 bondage number of a graph always ≤ 3Δ/2, where Δ is the maximum degree?...

Does every bridgeless graph have a nowhere-zero 5-flow?...

Does every Petersen-minor-free bridgeless graph have a nowhere-zero 4-flow?...

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

For any graph $H$ is there some $c=c(H)>0$ such that every graph $G$ on $n$ vertices that does not contain $H$ as an induced subgraph contains either ...

If $G_1,G_2$ are two graphs with chromatic number $\aleph_1$ then must there exist a graph $G$ whose chromatic number is $4$ (or even $\aleph_0$) whic...

Let $G$ be a graph with $n$ vertices and $kn$ edges, and $a_1<a_2<\cdots $ be the lengths of cycles in $G$. Is it true that $ \sum\frac{1}{a_i}\gg \lo...

Let $f(n)\to \infty$ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made...

Is there a graph of chromatic number $\aleph_1$ such that for all $\epsilon>0$ if $n$ is sufficiently large and $H$ is a subgraph on $n$ vertices then...

If $R(k)$ is the Ramsey number for $K_k$, the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$, ...

Give a constructive proof that $R(k)>C^k$ for some constant $C>1$....

Let $c>0$ and let $f_c(n)$ be the maximal $m$ such that every graph $G$ with $n$ vertices and at least $cn^2$ edges, where each edge is contained in a...

Let $F(n)$ be maximal such that every graph on $n$ vertices contains a regular induced subgraph on at least $F(n)$ vertices. Prove that $F(n)/\log n\t...

The cycle set of a graph $G$ on $n$ vertices is a set $A\subseteq \{3,\ldots,n\}$ such that there is a cycle in $G$ of length $\ell$ if and only if $\...

Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that every subgraph of $Q_n$ with...

Let $\epsilon >0$. Is it true that, if $k$ is sufficiently large, then $ R(G)>(1-\epsilon)^kR(k) $ for every graph $G$ with chromatic number $\chi(G)=...

Does every set of $n$ distinct points in $\mathbb{R}^2$ contain at most $n^{1+O(1/\log\log n)}$ many pairs which are distance 1 apart?...

Let $f(n)$ be maximal such that there exists a set $A$ of $n$ points in $\mathbb{R}^2$ in which every $x\in A$ has at least $f(n)$ points in $A$ equid...

If $n$ points in $\mathbb{R}^2$ form a convex polygon then there are $O(n)$ many pairs which are distance $1$ apart....

Let $A\subseteq\mathbb{R}^2$ be a set of $n$ points with minimum distance equal to 1, chosen to minimise the diameter of $A$. If $n$ is sufficiently l...

Given $n$ points in $\mathbb{R}^2$ the number of distinct unit circles containing at least three points is $o(n^2)$....

For every $r\geq 4$ and $k\geq 2$ is there some finite $f(k,r)$ such that every graph of chromatic number $\geq f(k,r)$ contains a subgraph of girth $...

If $G$ is a graph let $h_G(n)$ be defined such that any subgraph of $G$ on $n$ vertices can be made bipartite after deleting at most $h_G(n)$ edges. W...

If $p(z)\in\mathbb{C}[z]$ is a monic polynomial of degree $n$ then is the length of the curve $\{ z\in \mathbb{C} : \lvert p(z)\rvert=1\}$ maximised w...

Let $R(n;k,r)$ be the smallest $N$ such that if the edges of $K_N$ are $r$-coloured then there is a set of $n$ vertices which does not contain a copy ...

Let $A\subset \mathbb{R}^2$ be a set of $n$ points. Must there be two distances which occur at least once but between at most $n$ pairs of points? Mus...

Let $G$ be a graph with maximum degree $\Delta$. Is $G$ the union of at most $\tfrac{5}{4}\Delta^2$ sets of strongly independent edges (sets such that...

For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ on at least two vertices...

There exists some constant $c>0$ such that $$R(C_4,K_n) \ll n^{2-c}.$$...

Let $\alpha\in[0,1/2)$ and $n,t\geq 1$. Let $F^{(t)}(n,\alpha)$ be the smallest $m$ such that we can $2$-colour the edges of the complete $t$-uniform ...

Let $\alpha>0$ and $n\geq 1$. Let $F(n,\alpha)$ be the largest $k$ such that there exists some 2-colouring of the edges of $K_n$ in which any induced ...

Give an asymptotic formula for $R(3,k)$....

In any $2$-colouring of $\mathbb{R}^2$, for all but at most one triangle $T$, there is a monochromatic congruent copy of $T$....

If $\mathcal{F}$ is a finite set of finite graphs then $\mathrm{ex}(n;\mathcal{F})$ is the maximum number of edges a graph on $n$ vertices can have wi...

Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Prove that $ R(Q_n) \ll 2^n. $ ...