Unsolved Problems

Problem Is it true for all $n \ge 0$, that every sufficiently large $n$-connected graph without a $K_n$ minor has a set of $n-5$ vertices whose deleti...

Conjecture Every 6-connected graph without a $K_6$ minor is apex (planar plus one vertex)....

Conjecture Every $n$ vertex graph with no independent set of size $3$ has a complete graph on $\ge \frac{n}{2}$ vertices as a minor....

Conjecture Every simple connected graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n+1)$ paths....

Conjecture The minimum $k$-norm of a path partition on a directed graph $D$ is no more than the maximal size of an induced $k$-colorable subgraph....

Conjecture A total coloring of a graph $G = (V,E)$ is an assignment of colors to the vertices and the edges of $G$ such that every pair of adjacent ve...

Conjecture Let $G$ be a cubic graph with no bridge. Then there is a coloring of the edges of $G$ using the edges of the Petersen graph so that any thr...

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

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 All trees are graceful...

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

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

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

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

Conjecture Every planar graph is acyclically 5-choosable....

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 directed graph with smallest directed cut of size $k$, then $G$ has $k$ disjoint dijoins....

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

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

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 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 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 fixed graph $H$, there exists a constant $\delta(H)$, so that every graph $G$ without an induced subgraph isomorphic to $H$ conta...

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

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

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

An alternating walk in a digraph is a walk $v_0,e_1,v_1,\ldots,v_m$ so that the vertex $v_i$ is either the head of both $e_i$ and $e_{i+1}$ or the tai...

If $G$ is a graph, we say that a partition of $V(G)$ is unfriendly if every vertex has at least as many neighbors in the other classes as in its own. ...

Let $H$ be a hypergraph. A strongly maximal matching is a matching $F \subseteq E(H)$ so that $|F' \setminus F| \le |F \setminus F'|$ for every matchi...

Call a graph an $(\aleph_0,\aleph_1)$-graph if it has a bipartition $(A,B)$ so that every vertex in $A$ has degree $\aleph_0$ and every vertex in $B$ ...

Conjecture If $G$ is a simple loopless triangulation of an orientable surface, then the dual of $G$ is 3-edge-colorable....