Unsolved Problems

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

Question Given $a,b\geq2$, what is the smallest integer $t\geq0$ such that $\chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t)$?...

Conjecture Every $K_t$-minor-free graph is $c t$-list-colourable for some constant $c\geq1$....

Conjecture If $\chi(G)>k$, then $G$ contains at least $\frac{(k+1)(k-1)!}{2}$ cycles of length $0\bmod k$....

Conjecture If $G$ is an orientation of a simple planar graph, then there is a partition of $V(G)$ into $\{X_1,X_2\}$ so that the graph induced by $X_i...

Conjecture If $G$ is a directed graph with smallest directed cut of size $k$, then $G$ has $k$ disjoint dijoins....

Conjecture For every positive integer $k$, every digraph with minimum out-degree at least $2k-1$ contains $k$ disjoint cycles....

Conjecture Any oriented graph has a vertex whose outdegree is at most its second outdegree....

For any simple digraph $G$, we let $\gamma(G)$ be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and $\beta(G)$...

Conjecture Every digraph with chromatic number at least $2k-2$ contains every oriented tree of order $k$ as a subdigraph....

An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0. Conjecture Let $D$ be a digraph. If $|A...

Conjecture Every oriented graph with minimum outdegree $k$ contains a directed path of length $2k$....

Conjecture Every simple digraph of order $n$ with minimum outdegree at least $r$ has a cycle with length at most $\lceil n/r\rceil$...

Conjecture Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles....

Problem Is there a minimum integer $f(d)$ such that the vertices of any digraph with minimum outdegree $d$ can be partitioned into two classes so that...

Conjecture Every strong oriented graph in which each vertex has indegree and outdegree at least $d$ contains a directed cycle of length at least $2d+1...

Conjecture There exists an integer $k$ such that every $k$-arc-strong digraph $D$ with specified vertices $u$ and $v$ contains an out-branching rooted...

Conjecture For all $k$ there is an integer  $f(k)$ such that every digraph of minimum outdegree at least  $f(k)$ contains a subdivision of a transit...

An directed graph is $k$-diregular if every vertex has indegree and outdegree at least $k$. Conjecture For $d >2$, every $d$-diregular oriented graph...

Conjecture Every digraph in which each vertex has outdegree at least $k$ contains $k$ directed cycles $C_1, \ldots, C_k$ such that $C_j$ meets $\cup_{...

Conjecture If $G$ is a $k$-regular directed graph with no parallel arcs, then $G$ contains a collection of ${k+1 \choose 2}$ arc-disjoint directed cyc...

Conjecture Let $D$ be a digraph all of whose strong components are nontrivial. Then $D$ contains a cyclic spanning subdigraph with cyclomatic number a...

Conjecture Every planar oriented graph $D$ has an acyclic induced subdigraph of order at least $\frac{3}{5} |V(D)|$....

Conjecture Let $\ell \geq 2$ be an integer. For every integer $n\geq 0$, there exists an integer $t_n=t_n(\ell)$ such that for every digraph $D$, eith...

Conjecture For every $k$, there exists an integer $f(k)$ such that if $D$ is a digraph whose arcs are colored with $k$ colors, then $D$ has a $S$ set ...