Unsolved Problems

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

Conjecture Every graph with minimum degree at least 7 contains a $K_6$-minor. Conjecture Every 7-connected graph contains a $K_6$-minor....

Conjecture Every graph with average degree at least $\frac{4}{3}t-2$ contains every 2-regular graph on $t$ vertices as a minor....

Problem Does every $3$-connected cubic graph on $3k$ vertices admit a partition into $k$ paths of length $2$?...

Question Are there any (0,2)-graphs with chromatic number exactly three?...

Problem Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth?...

Conjecture The union of a $1$-degenerate graph (a forest) and a $2$-degenerate graph is $5$-colourable....

Conjecture If $G$ is the total graph of a multigraph, then $\chi_\ell(G)=\chi(G)$....

Conjecture There exists a fixed constant $c$ (probably $c=1$ suffices) so that every graft with minimum $T$-cut size at least $k$ contains a $T$-join ...

Conjecture Every simple graph with maximum degree $\Delta$ has a proper $(\Delta+2)$-edge-colouring so that every cycle contains edges of at least thr...

Conjecture Let $H$ be a simple $d$-uniform hypergraph, and assume that every set of $d-1$ points is contained in at most $r$ edges. Then there exists ...

Conjecture Suppose that $G$ is a $\Delta$-edge-critical graph. Suppose that for each edge $e$ of $G$, there is a list $L(e)$ of $\Delta$ colors. Then ...

Problem Which Steiner triple systems are universal?...

A strong edge-colouring of a graph $G$ is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to ...

Conjecture Let $M$ be an abelian group. Is the core of a Cayley graph (on some power of $M$ ) a Cayley graph (on some power of $M$ )?...

Conjecture If $G$ is a cubic graph not containing a triangle, then it is possible to color the edges of $G$ by five colors, so that the complement of ...

Question Is there an algorithm that decides, for input graphs $G$ and $H$, whether there exists a homomorphism from $G$ to $H$ in time $O(c^{|V(G)|+|...

Let $G = (V, E)$ be a graph. If $p$ and $q$ are two integers, a $(p,q)$-colouring of $G$ is a function $c$ from $V$ to $\{0,\dots,p-1\}$ such that $q ...

Question What is the maximum edge density of a graph which has a good edge labeling? We say that a graph is good-edge-labeling critical, if it has no...

Conjecture For every graph $G$ with no bridge, there exist three disjoint sets $A_1,A_2,A_3 \subseteq E(G)$ with $A_1 \cup A_2 \cup A_3 = E(G)$ so tha...

Conjecture Let $M,M'$ be abelian groups and let $B \subseteq M$ and $B' \subseteq M'$ satisfy $B=-B$ and $B' = -B'$. If there is a homomorphism from $...

Conjecture All real roots of nonzero flow polynomials are at most 4....

Conjecture For every graph $G$ without a bridge, there is a flow $\phi: E(G) \rightarrow S^2 = \{ x \in {\mathbb R}^3: |x| = 1 \}$. Conjecture There ...

If $G$, $H$ are graphs, a function $f: E(G) \rightarrow E(H)$ is called cycle-continuous if the pre-image of every element of the (binary) cycle space...

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

Problem Does every triangle-free planar graph of maximum degree three have circular chromatic number at most $\frac{20}{7}$?...

An oriented colouring of an oriented graph is assignment $c$ of colours to the vertices such that no two arcs receive ordered pairs of colours $(c_1,c...

Problem Find $\lim_{n \rightarrow \infty} (\chi( H_n, 3)) ^{ 1 / |V(H_n)| }$....

Let ${\mathcal O}$ denote the graph with vertex set consisting of all lines through the origin in ${\mathbb R}^3$ and two vertices adjacent in ${\math...

A connected simple graph $G$ is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two. Conjecture $K_n...

Conjecture A triangle-free graph with maximum degree $\Delta$ has chromatic number at most $\ceil{\frac{\Delta}{2}}+2$....

Question Is every proper vertex-minor closed class of graphs chi-bounded?...

Question Is $\mathfrak{M}_c(G)$ always rational?...

Conjecture If $G$ is a $k$-chromatic graph on at most $mk$ vertices, then $\text{ch}(G)\leq \text{ch}(K_{m*k})$....

Problem The valency-variety $w(G)$ of a graph $G$ is the number of different degrees in $G$. Is the chromatic number of any graph $G$ with at least tw...

Problem What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in th...

Conjecture There is a constant $c$ such that the list chromatic number of any bipartite graph $G$ of maximum degree $\Delta$ is at most $c \log \Delta...

Conjecture Let $G$ be a planar graph of maximum degree $\Delta$. The chromatic number of its square is - at most $7$ if $\Delta =3$, - at most $\Delt...

Conjecture There is an absolute constant $c$ such that for every hexagonal graph $G$ and vertex weighting $p:V(G)\rightarrow \mathbb{N}$, $$\chi(G,p) ...

Question Are there graphs for which $\text{ch}^{\text{OL}}-\text{ch}$ is arbitrarily large?...