Unsolved Problems

We let $p(G)$ denote the pebbling number of a graph $G$. Conjecture $p(G_1 \Box G_2) \le p(G_1) p(G_2)$....

Conjecture Every simple graph with at least 4 edges is reconstructible from it's edge deleted subgraphs...

Problem What is the Shannon capacity of $C_7$?...

Given integers $k,n \ge 2$, the 2-stage Shuffle-Exchange graph/network, denoted $\text{SE}(k,n)$, is the simple $k$-regular bipartite graph with the o...

Problem ( $\dag$ ) Find a sufficient condition for a straight $\ell$-stage graph to be rearrangeable. In particular, what about a straight uniform gra...

Conjecture Let $G$ be a graph and $k$ be a positive integer. The $k-$ power of $G$, denoted by $G^k$, is defined on the vertex set $V(G)$, by connecti...

Problem Are almost all graphs uniquely determined by the spectrum of their adjacency matrix?...

Conjecture (3-Decomposition Conjecture) Every connected cubic graph $G$ has a decomposition into a spanning tree, a family of cycles and a matching....

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

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

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

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

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

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

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

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