Unsolved Problems

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

In an edge-colored digraph, we say that a subgraph is rainbow if all its edges have distinct colors, and monochromatic if all its edges have the same ...

Conjecture Every tournament $D$ on an even number of vertices can be decomposed into $\sum_{v\in V}\max\{0,d^+(v)-d^-(v)\}$ directed paths....

Conjecture For every $k\geq 2$, there is an integer $f(k)$ so that every strongly $f(k)$-connected tournament has $k$ edge-disjoint Hamilton cycles....

Problem Let $k_1, \dots, k_p$ be positve integer Does there exists an integer $g(k_1, \dots, k_p)$ such that every $g(k_1, \dots, k_p)$-strong tournam...

Conjecture Every k-arc-strong tournament decomposes into k spanning strong digraphs....

Conjecture For every fixed graph $H$, there exists a constant $\delta(H)$, so that every graph $G$ without an induced subgraph isomorphic to $H$ conta...

We are given a complete simple undirected weighted graph $G_1=(V,E)$ and its first arbitrary shortest spanning tree $T_1=(V,E_1)$. We define the next ...

Conjecture An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the $n$ vertices' trees, the star w...

An $H$-factor in a graph $G$ is a set of vertex-disjoint copies of $H$ covering all vertices of $G$. Problem Let $c$ be a fixed positive real number ...

Conjecture If $G$ is a simple triangle-free graph, then there is a set of at most $n^2/25$ edges whose deletion destroys every odd cycle....

Conjecture If $G$ has at most $k$ edge-disjoint triangles, then there is a set of $2k$ edges whose deletion destroys every triangle....

Conjecture (BEC-conjecture) If $G_1$ and $G_2$ are $n$-vertex graphs and $(\Delta(G_1) + 1) (\Delta(G_2) + 1) < n + 1$, then $G_1$ and $G_2$ pack....

Problem Determine $\text{wsat}(K_n,Q_3)$....

Conjecture For every fixed $k\geq2$ and fixed colouring $\chi$ of $E(K_k)$ with $m$ colours, there exists $\varepsilon>0$ such that every colouring of...

Setup Fix a tree $T$ and for every vertex $v \in V(T)$ a non-negative integer $g(v)$ which we think of as the amount of gold at $v$. 2-Player game Pl...

Question Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?...

Conjecture Let $H$ be an $r$-uniform $r$-partite hypergraph. If $\nu$ is the maximum number of pairwise disjoint edges in $H$, and $\tau$ is the size ...

Conjecture Let $H$ be a $k$-uniform hypergraph. If $H$ is a critical $k$-forest, then it is a $k$-tree....

Conjecture Let $F$ be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists $x$ such that $x$ is an ele...

Problem Let $H_1$ and $H_2$ be two $r$-uniform hypergraph on the same vertex set $V$. Does there always exist a partition of $V$ into $r$ classes $V_1...

Conjecture Every simple $3$-uniform hypergraph on $3n$ vertices which contains no complete $3$-uniform hypergraph on four vertices has at most $\frac1...

Conjecture Every infinite graph is a proper minor of itself....

Problem Does there exist a graph with no subgraph isomorphic to $K_4$ which cannot be expressed as a union of $\aleph_0$ triangle free graphs?...

Problem Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree $r > 2$?...

Conjecture - If $G$ is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. - If the line graph $L(G)$ of a locally finite gr...

Conjecture - If $G$ is a countable connected graph then its third power is hamiltonian. - If $G$ is a 2-connected countable graph then its square is ...