Nearly spanning regular subgraphs
Conjecture For every $\epsilon > 0$ and every positive integer $k$, there exists $r_0 = r_0(\epsilon,k)$ so that every simple $r$-regular graph $G$ wi...
Complete bipartite subgraphs of perfect graphs
Problem Let $G$ be a perfect graph on $n$ vertices. Is it true that either $G$ or $\bar{G}$ contains a complete bipartite subgraph with bipartition $(...
Asymptotic Distribution of Form of Polyhedra
Problem Consider the set of all topologically inequivalent polyhedra with $k$ edges. Define a form parameter for a polyhedron as $\beta:= v/(k+2)$ whe...
Domination in cubic graphs
Problem Does every 3-connected cubic graph $G$ satisfy $\gamma(G) \le \lceil |G|/3 \rceil$?...
Friendly partitions
A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as ...
Subgraph of large average degree and large girth.
Conjecture For all positive integers $g$ and $k$, there exists an integer $d$ such that every graph of average degree at least $d$ contains a subgraph...
Almost all non-Hamiltonian 3-regular graphs are 1-connected
Conjecture Denote by $NH(n)$ the number of non-Hamiltonian 3-regular graphs of size $2n$, and similarly denote by $NHB(n)$ the number of non-Hamiltoni...
Partitioning edge-connectivity
Question Let $G$ be an $(a+b+2)$-edge-connected graph. Does there exist a partition $\{A,B\}$ of $E(G)$ so that $(V,A)$ is $a$-edge-connected and $(V,...
Kriesell's Conjecture
Conjecture Let $G$ be a graph and let $T\subseteq V(G)$ such that for any pair $u,v\in T$ there are $2k$ edge-disjoint paths from $u$ to $v$ in $G$. T...
Cycle double cover conjecture
Conjecture For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two....
The circular embedding conjecture
Conjecture Every 2-connected graph may be embedded in a surface so that the boundary of each face is a cycle....
(m,n)-cycle covers
Conjecture Every bridgeless graph has a (5,2)-cycle-cover....
Faithful cycle covers
Conjecture If $G = (V,E)$ is a graph, $p: E \rightarrow {\mathbb Z}$ is admissable, and $p(e)$ is even for every $e \in E(G)$, then $(G,p)$ has a fait...
Decomposing eulerian graphs
Conjecture If $G$ is a 6-edge-connected Eulerian graph and $P$ is a 2-transition system for $G$, then $(G,P)$ has a compaible decomposition....
Barnette's Conjecture
Conjecture Every 3-connected cubic planar bipartite graph is Hamiltonian....
r-regular graphs are not uniquely hamiltonian.
Conjecture If $G$ is a finite $r$-regular graph, where $r > 2$, then $G$ is not uniquely hamiltonian....
Hamiltonian cycles in line graphs
Conjecture Every 4-connected line graph is hamiltonian....
Geodesic cycles and Tutte's Theorem
Problem If $G$ is a $3$-connected finite graph, is there an assignment of lengths $\ell: E(G) \to \mathb R^+$ to the edges of $G$, such that every $\e...
Jones' conjecture
For a graph $G$, let $cp(G)$ denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let $cc(G)$ denote the cardi...
Chords of longest cycles
Conjecture If $G$ is a 3-connected graph, every longest cycle in $G$ has a chord....
Hamiltonicity of Cayley graphs
Question Is every Cayley graph Hamiltonian?...
Strong 5-cycle double cover conjecture
Conjecture Let $C$ be a circuit in a bridgeless cubic graph $G$. Then there is a five cycle double cover of $G$ such that $C$ is a subgraph of one of ...
Decomposing an eulerian graph into cycles.
Conjecture Every simple eulerian graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n-1)$ cycles....
Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour.
Conjecture Let $G$ be an eulerian graph of minimum degree $4$, and let $W$ be an eulerian tour of $G$. Then $G$ admits a decomposition into cycles non...
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?...