Every prism over a 3-connected planar graph is hamiltonian.
Conjecture If $G$ is a $3$-connected planar graph, then $G\square K_2$ has a Hamilton cycle....
4-connected graphs are not uniquely hamiltonian
Conjecture Every $4$-connected graph with a Hamilton cycle has a second Hamilton cycle....
Hamilton decomposition of prisms over 3-connected cubic planar graphs
Conjecture Every prism over a $3$-connected cubic planar graph can be decomposed into two Hamilton cycles....
The Berge-Fulkerson conjecture
Conjecture If $G$ is a bridgeless cubic graph, then there exist 6 perfect matchings $M_1,\ldots,M_6$ of $G$ with the property that every edge of $G$ i...
The intersection of two perfect matchings
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....
Matchings extend to Hamiltonian cycles in hypercubes
Question Does every matching of hypercube extend to a Hamiltonian cycle?...
Random stable roommates
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/...
Highly connected graphs with no K_n minor
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...
Jorgensen's Conjecture
Conjecture Every 6-connected graph without a $K_6$ minor is apex (planar plus one vertex)....
Seagull problem
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....
Forcing a $K_6$-minor
Conjecture Every graph with minimum degree at least 7 contains a $K_6$-minor. Conjecture Every 7-connected graph contains a $K_6$-minor....
Forcing a 2-regular 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....
Decomposing a connected graph into paths.
Conjecture Every simple connected graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n+1)$ paths....
Partition of a cubic 3-connected graphs into paths of length 2.
Problem Does every $3$-connected cubic graph on $3k$ vertices admit a partition into $k$ paths of length $2$?...
Linial-Berge path partition duality
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....
Three-chromatic (0,2)-graphs
Question Are there any (0,2)-graphs with chromatic number exactly three?...
Total Colouring Conjecture
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...
4-regular 4-chromatic graphs of high girth
Problem Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth?...
Coloring the union of degenerate graphs
Conjecture The union of a $1$-degenerate graph (a forest) and a $2$-degenerate graph is $5$-colourable....
List Total Colouring Conjecture
Conjecture If $G$ is the total graph of a multigraph, then $\chi_\ell(G)=\chi(G)$....
Petersen coloring conjecture
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...
Packing T-joins
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 ...
Acyclic edge-colouring
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...
A generalization of Vizing's Theorem?
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 ...
List colorings of edge-critical graphs
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 ...
Universal Steiner triple systems
Problem Which Steiner triple systems are universal?...
Edge list coloring conjecture
Conjecture Let $G$ be a loopless multigraph. Then the edge chromatic number of $G$ equals the list edge chromatic number of $G$....
Seymour's r-graph conjecture
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) ...
Goldberg's conjecture
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\...
Strong edge colouring conjecture
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 ...
Cores of Cayley graphs
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$ )?...
Pentagon problem
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...
Mapping planar graphs to odd cycles
Conjecture Every planar graph of girth $\ge 4k$ has a homomorphism to $C_{2k+1}$....
Weak pentagon problem
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 ...
Algorithm for graph homomorphisms
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)|+|...
Circular choosability of planar graphs
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 ...
Graceful Tree Conjecture
Conjecture All trees are graceful...
Good Edge Labelings
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...
5-flow conjecture
Conjecture Every bridgeless graph has a nowhere-zero 5-flow....
4-flow conjecture
Conjecture Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow....
3-flow conjecture
Conjecture Every 4-edge-connected graph has a nowhere-zero 3-flow....
Jaeger's modular orientation conjecture
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...
Bouchet's 6-flow conjecture
Conjecture Every bidirected graph with a nowhere-zero $k$-flow for some $k$, has a nowhere-zero $6$-flow....
The three 4-flows conjecture
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...
A homomorphism problem for flows
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 $...
Real roots of the flow polynomial
Conjecture All real roots of nonzero flow polynomials are at most 4....
Unit vector flows
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 ...
Antichains in the cycle continuous order
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...
Circular flow number of regular class 1 graphs
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...
Strong colorability
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...