Unsolved Problems

Let $G$ be a graph given by $n$ points in $\mathbb{R}^2$, where any two distinct points are at least distance $1$ apart, and we draw an edge between t...

Does every graph with chromatic number $\aleph_1$ contain a countable subgraph which is infinitely vertex-connected?...

Let $f(n)$ be maximal such that, given any $n$ points in $\mathbb{R}^2$, there exist $f(n)$ points such that no two are distance $1$ apart. Estimate $...

Let $r\geq 3$. There exists $c_r>r^{-r}$ such that, for any $\epsilon>0$, if $n$ is sufficiently large, the following holds. Any $r$-uniform hypergrap...

Let $f_d(n)$ be minimal such that, in any set of $n$ points in $\mathbb{R}^d$, there exist at most $f_d(n)$ pairs of points which distance $1$ apart. ...

Let $g(n)$ be minimal such that any set of $n$ points in $\mathbb{R}^2$ contains the vertices of at most $g(n)$ many triangles with the same area. Est...

Let $g_d(n)$ be minimal such that every collection of $g_d(n)$ points in $\mathbb{R}^d$ determines at least $n$ many distinct distances. Estimate $g_d...

Let $G$ be a $K_4$-free graph with chromatic number $4$. Must $G$ contain an odd cycle with at least two diagonals? More generally, is there some $f(r...

Let $f_r(n)$ be maximal such that, if a graph $G$ has the property that every subgraph $H$ on $m$ vertices is the union of a graph with chromatic numb...

Let $f(n)$ be the maximum possible chromatic number of a triangle-free graph on $n$ vertices. Estimate $f(n)$....

The anti-Ramsey number $\mathrm{AR}(n,G)$ is the maximum possible number of colours in which the edges of $K_n$ can be coloured without creating a rai...

If $G$ is a finite graph and $A,B$ are disjoint sets of vertices then we call $A,B$ anticomplete if there are no edges between $A$ and $B$. If $t,c\ge...

Let $f\in \mathbb{C}[z]$ be a monic polynomial of degree $n$, all of whose roots satisfy $\lvert z\rvert\leq 1$. Let $ E= \{ z : \lvert f(z)\rvert \le...

Let $C>0$. There exists $\epsilon>0$ such that if $n$ is sufficiently large the following holds. For any $x_1,\ldots,x_n\in [-1,1]$ there exist $y_1,\...

We let $p(G)$ denote the pebbling number of a graph $G$. Conjecture $p(G_1 \Box G_2) \le p(G_1) p(G_2)$....

The deck of a graph $G$ is the multiset consisting of all unlabelled subgraphs obtained from $G$ by deleting a vertex in all possible ways (counted ac...

Conjecture Every simple graph with at least 4 edges is reconstructible from it's edge deleted subgraphs...

Let $G$ be a finite undirected simple graph. A $k$-page book embedding of $G$ consists of a linear order $\preceq$ of $V(G)$ and a (non-proper) $k$-c...

Problem What is the Shannon capacity of $C_7$?...

Question Is there a constant $c$ such that every $n$-vertex $K_t$-minor-free graph has at most $c^tn$ cliques?...

Given integers $k,n \ge 2$, the 2-stage Shuffle-Exchange graph/network, denoted $\text{SE}(k,n)$, is the simple $k$-regular bipartite graph with the o...

Conjecture If in a bridgeless cubic graph $G$ the cycles of any $2$-factor are odd, then $\omega(G)\leq 2$, where $\omega(G)$ denotes the oddness of t...

Problem ( $\dag$ ) Find a sufficient condition for a straight $\ell$-stage graph to be rearrangeable. In particular, what about a straight uniform gra...

Conjecture Can the approximation ratio $O(\sqrt{n})$ be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapp...

Conjecture Is the approximation ratio for the Maximum Edge Disjoint Paths (MaxEDP) or the Maximum Integer Multiflow problem (MaxIMF) bounded by a cons...

Conjecture It has been shown that a $k$-outerplanar embedding for which $k$ is minimal can be found in polynomial time. Does a similar result hold for...

Conjecture For $c \geq m \geq 1$, let $P(c,m)$ be the statement that given any exact $c$-coloring of the edges of a complete countably infinite graph ...

The star chromatic index $\chi_s'(G)$ of a graph $G$ is the minimum number of colors needed to properly color the edges of the graph so that no path o...

Conjecture Is it possible to color edges of the complete graph $K_n$ using $O(n)$ colors, so that the coloring is proper and no 4-cycle and no 4-edge ...

Conjecture Let $G$ be a graph and $k$ be a positive integer. The $k-$ power of $G$, denoted by $G^k$, is defined on the vertex set $V(G)$, by connecti...

Conjecture Given $k$ and $n$, the graph $C_{n}^k$ has equivalence covering number $\Omega(k)$....

Does there exist a planar graph with obstacle number greater than 1? Is there some $k$ such that every planar graph has obstacle number at most $k$?...

Question For every $d$ does there exists a $g$ such that every graph with average degree smaller than $d$ and girth at least $g$ has a matching-cut?...

Conjecture Let $n \geq 3$ be an integer and let $\alpha(n)$ denote the least integer $k$ such that there exists a simple graph on $k$ vertices having ...

Conjecture Every graph with maximum degree $\Delta \geq 9$ has chromatic number at most $\max\{\Delta-1, \omega\}$....

Conjecture Every digraph has a stable set meeting all longest directed paths...

Conjecture There exists an ineteger $k$ so that every $k$-arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraph...

Conjecture Do any three longest paths in a connected graph have a vertex in common?...

Conjecture There is an integer-valued function $f(k)$ such that if $G$ is any $f(k)$-connected graph and $x$ and $y$ are any two vertices of $G$, then...

Given a finite family ${\cal F}$ of graphs and an integer $n$, the Turán number $ex(n,{\cal F})$ of ${\cal F}$ is the largest integer $m$ such that th...

Conjecture Every simple graph on five or more vertices is switching-reconstructible....

Question Are there any switching-nonreconstructible digraphs on twelve or more vertices?...

Conjecture If $A$ is the adjacency matrix of a $d$-regular graph, then there is a symmetric signing of $A$ (i.e. replace some $+1$ entries by $-1$ ) s...

Problem Are almost all graphs uniquely determined by the spectrum of their adjacency matrix?...

Conjecture If $T$ is a tournament of order $n$, then it contains $\left \lceil n(n-1)/6 - n/3\right\rceil$ arc-disjoint transitive subtournaments of o...

Conjecture Suppose that for all edges $e\in E(G)$ we have $imb(e)>0$. Then $M_{G}$ is graphic....

Conjecture For every graph $G$, (a) $\chi_f(G)\leq\text{had}(G)$ (b) $\chi(G)\leq\text{had}_f(G)$ (c) $\chi_f(G)\leq\text{had}_f(G)$....

Question Do common graphs have bounded chromatic number?...

A nowhere-zero $r$-flow $(D(G),\phi)$ on $G$ is an orientation $D$ of $G$ together with a function $\phi$ from the edge set of $G$ into the real numbe...

Conjecture (3-Decomposition Conjecture) Every connected cubic graph $G$ has a decomposition into a spanning tree, a family of cycles and a matching....