Unsolved Problems

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

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

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

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

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

Let $G$ be a graph and $m,n\in \mathbb{N}$. The graph $G^{\frac{m}{n}}$ is defined to be the $m$-power of the $n$-subdivision of $G$. In other words, ...

Let $\Phi(G,x)$ be the flow polynomial of a graph $G$. So for every positive integer $k$, the value $\Phi(G,k)$ equals the number of nowhere-zero $k$-...

Conjecture If $G$ is a connected graph on $n$ vertices, then $c_k(G) \ge d_k(G)$ for $k = 1, 2, \dots, n-1$....

Problem Do there exist non-isomorphic trees which have the same chromatic symmetric function?...

Problem for every graph $G$, we let $L(G)$ denote the line graph of $G$. Given that $G$ is a tree, can we determine it from the integer sequence $|V(G...

Problem Let $G$ be a perfect graph on $n$ vertices. Is it true that either $G$ or $\bar{G}$ contains a complete bipartite subgraph with bipartition $(...

Problem Consider the set of all topologically inequivalent polyhedra with $k$ edges. Define a form parameter for a polyhedron as $\beta:= v/(k+2)$ whe...

Problem Does every 3-connected cubic graph $G$ satisfy $\gamma(G) \le \lceil |G|/3 \rceil$?...

A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as ...

Conjecture For all positive integers $g$ and $k$, there exists an integer $d$ such that every graph of average degree at least $d$ contains a subgraph...

Conjecture Denote by $NH(n)$ the number of non-Hamiltonian 3-regular graphs of size $2n$, and similarly denote by $NHB(n)$ the number of non-Hamiltoni...

Question Let $G$ be an $(a+b+2)$-edge-connected graph. Does there exist a partition $\{A,B\}$ of $E(G)$ so that $(V,A)$ is $a$-edge-connected and $(V,...

Conjecture Let $G$ be a graph and let $T\subseteq V(G)$ such that for any pair $u,v\in T$ there are $2k$ edge-disjoint paths from $u$ to $v$ in $G$. T...

Problem If $G$ is a $3$-connected finite graph, is there an assignment of lengths $\ell: E(G) \to \mathb R^+$ to the edges of $G$, such that every $\e...

For a graph $G$, let $cp(G)$ denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let $cc(G)$ denote the cardi...

Conjecture Every simple eulerian graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n-1)$ cycles....

Conjecture Let $G$ be an eulerian graph of minimum degree $4$, and let $W$ be an eulerian tour of $G$. Then $G$ admits a decomposition into cycles non...

Conjecture If $G$ is a $3$-connected planar graph, then $G\square K_2$ has a Hamilton cycle....

Conjecture Every $4$-connected graph with a Hamilton cycle has a second Hamilton cycle....

Conjecture Every prism over a $3$-connected cubic planar graph can be decomposed into two Hamilton cycles....

Conjecture Every bridgeless cubic graph has two perfect matchings $M_1$, $M_2$ so that $M_1 \cap M_2$ does not contain an odd edge-cut....

Question Does every matching of hypercube extend to a Hamiltonian cycle?...

Conjecture The probability that a random instance of the stable roommates problem on $n \in 2{\mathbb N}$ people admits a solution is $\Theta( n ^{-1/...