Unsolved Problems

Conjecture Let $G$ be a $2$-connected cubic graph and let $S$ be a $2$-regular subgraph such that $G-E(S)$ is connected. Then $G$ has a cycle double c...

Conjecture For which values of $n$ and $d$ are there bi-colored graphs on $n$ vertices and $d$ different colors with the property that all the $d$ mon...

Conjecture For any bipartite graph $H$ and graph $G$, the number of homomorphisms from $H$ to $G$ is at least $\left(\frac{2|E(G)|}{|V(G)|^2}\right)^{...

Conjecture Suppose $G$ with $|V(G)|>2$ is a connected cubic graph admitting a $3$-edge coloring. Then there is an edge $e \in E(G)$ such that the cubi...

Let $G$ be a graph and $m,n\in \mathbb{N}$. The graph $G^{\frac{m}{n}}$ is defined to be the $m$-power of the $n$-subdivision of $G$. In other words, ...

Question Does there exist a 57-regular graph with diameter 2 and girth 5?...

Problem Does every connected vertex-transitive graph have a Hamiltonian path?...

Problem Is there an eighth triangle free strongly regular graph?...

Let $\Phi(G,x)$ be the flow polynomial of a graph $G$. So for every positive integer $k$, the value $\Phi(G,k)$ equals the number of nowhere-zero $k$-...

Conjecture There exists a fixed constant $c$ so that every abelian group $G$ has a subset $S \subseteq G$ with $-S = S$ so that the Cayley graph ${\ma...

Conjecture If $G$ is a connected graph on $n$ vertices, then $c_k(G) \ge d_k(G)$ for $k = 1, 2, \dots, n-1$....

Question Does every strongly regular graph have either itself or a complete graph as a core?...

Problem Do there exist non-isomorphic trees which have the same chromatic symmetric function?...

Problem for every graph $G$, we let $L(G)$ denote the line graph of $G$. Given that $G$ is a tree, can we determine it from the integer sequence $|V(G...

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

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

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

Problem Does every 3-connected cubic graph $G$ satisfy $\gamma(G) \le \lceil |G|/3 \rceil$?...

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

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

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

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

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

Conjecture For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two....

Conjecture Every 2-connected graph may be embedded in a surface so that the boundary of each face is a cycle....

Conjecture Every bridgeless graph has a (5,2)-cycle-cover....

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

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

Conjecture Every 3-connected cubic planar bipartite graph is Hamiltonian....

Conjecture If $G$ is a finite $r$-regular graph, where $r > 2$, then $G$ is not uniquely hamiltonian....

Conjecture Every 4-connected line graph is hamiltonian....

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

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

Conjecture If $G$ is a 3-connected graph, every longest cycle in $G$ has a chord....

Question Is every Cayley graph Hamiltonian?...

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

Conjecture Every simple eulerian graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n-1)$ cycles....

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

Conjecture If $G$ is a $3$-connected planar graph, then $G\square K_2$ has a Hamilton cycle....

Conjecture Every $4$-connected graph with a Hamilton cycle has a second Hamilton cycle....

Conjecture Every prism over a $3$-connected cubic planar graph can be decomposed into two Hamilton cycles....

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

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

Question Does every matching of hypercube extend to a Hamiltonian cycle?...

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

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 graph with minimum degree at least 7 contains a $K_6$-minor. Conjecture Every 7-connected graph contains a $K_6$-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....