Unsolved Problems

Conjecture There is an integer-valued function $f(k)$ such that if $G$ is any $f(k)$-connected graph and $x$ and $y$ are any two vertices of $G$, then...

Given a finite family ${\cal F}$ of graphs and an integer $n$, the Turán number $ex(n,{\cal F})$ of ${\cal F}$ is the largest integer $m$ such that th...

Conjecture Every simple graph on five or more vertices is switching-reconstructible....

Question Are there any switching-nonreconstructible digraphs on twelve or more vertices?...

Conjecture If $A$ is the adjacency matrix of a $d$-regular graph, then there is a symmetric signing of $A$ (i.e. replace some $+1$ entries by $-1$ ) s...

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

Conjecture If $T$ is a tournament of order $n$, then it contains $\left \lceil n(n-1)/6 - n/3\right\rceil$ arc-disjoint transitive subtournaments of o...

Conjecture Suppose that for all edges $e\in E(G)$ we have $imb(e)>0$. Then $M_{G}$ is graphic....

Conjecture For every graph $G$, (a) $\chi_f(G)\leq\text{had}(G)$ (b) $\chi(G)\leq\text{had}_f(G)$ (c) $\chi_f(G)\leq\text{had}_f(G)$....

Question Do common graphs have bounded chromatic number?...

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

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

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