Unsolved Problems

Conjecture Let $G$ be a loopless multigraph. Then the edge chromatic number of $G$ equals the list edge chromatic number of $G$....

An $r$-graph is an $r$-regular graph $G$ with the property that $|\delta(X)| \ge r$ for every $X \subseteq V(G)$ with odd size. Conjecture $\chi'(G) ...

The overfull parameter is defined as follows: $$ w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\...

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

Question Let $G$ be a 3-regular graph that contains no cycle of length shorter than $g$. Is it true that for large enough~ $g$ there is a homomorphism...

Conjecture Every planar graph of girth $\ge 4k$ has a homomorphism to $C_{2k+1}$....

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

Conjecture All trees are graceful...

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 Every bridgeless graph has a nowhere-zero 5-flow....

Conjecture Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow....

Conjecture Every 4-edge-connected graph has a nowhere-zero 3-flow....

Conjecture Every $4k$-edge-connected graph can be oriented so that ${\mathit indegree}(v) - {\mathit outdegree}(v) \cong 0$ (mod $2k+1$ ) for every ve...

Conjecture Every bidirected graph with a nowhere-zero $k$-flow for some $k$, has a nowhere-zero $6$-flow....

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

Let $r$ be a positive integer. We say that a graph $G$ is strongly $r$-colorable if for every partition of the vertices to sets of size at most $r$ th...

For a graph $G$, we define $\Delta(G)$ to be the maximum degree, $\omega(G)$ to be the size of the largest clique subgraph, and $\chi(G)$ to be the ch...

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

Conjecture For every positive integer $t$, every (loopless) graph $G$ with $\chi(G) \ge t$ immerses $K_t$....

The Odd Distance Graph, denoted ${\mathcal O}$, is the graph with vertex set ${\mathbb R}^2$ and two points adjacent if the distance between them is a...

Conjecture Let $G$ be a simple graph with $n$ vertices and list chromatic number $\chi_\ell(G)$. Suppose that $0\leq t\leq \chi_\ell$ and each vertex ...

Let $G$ be a simple graph, and for every list assignment $\mathcal{L}$ let $\lambda_{\mathcal{L}}$ be the maximum number of vertices of $G$ which are ...

Conjecture If $G,H$ are simple finite graphs, then $\chi(G \times H) = \min \{ \chi(G), \chi(H) \}$. Here $G \times H$ is the tensor product (also ca...

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

Say that a family ${\mathcal F}$ of graphs is $\chi$-bounded if there exists a function $f: {\mathbb N} \rightarrow {\mathbb N}$ so that every $G \in ...

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 Every planar graph is acyclically 5-choosable....

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

Question (Noel, 2013) Does there exist a function $f(k)=o(k^2)$ such that for every graph $G$, $$ \text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\r...

Conjecture If $G$ is a simple graph which is the union of $k$ pairwise edge-disjoint complete graphs, each of which has $k$ vertices, then the chromat...

Conjecture If $G$ is a non-empty graph containing no induced odd cycle of length at least $5$, then there is a $2$-vertex colouring of $G$ in which no...