Unsolved Problems

Conjecture For $c \geq m \geq 1$, let $P(c,m)$ be the statement that given any exact $c$-coloring of the edges of a complete countably infinite graph ...

The star chromatic index $\chi_s'(G)$ of a graph $G$ is the minimum number of colors needed to properly color the edges of the graph so that no path o...

Conjecture Is it possible to color edges of the complete graph $K_n$ using $O(n)$ colors, so that the coloring is proper and no 4-cycle and no 4-edge ...

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

Conjecture Given $k$ and $n$, the graph $C_{n}^k$ has equivalence covering number $\Omega(k)$....

Does there exist a planar graph with obstacle number greater than 1? Is there some $k$ such that every planar graph has obstacle number at most $k$?...

Question For every $d$ does there exists a $g$ such that every graph with average degree smaller than $d$ and girth at least $g$ has a matching-cut?...

Conjecture Let $n \geq 3$ be an integer and let $\alpha(n)$ denote the least integer $k$ such that there exists a simple graph on $k$ vertices having ...

Conjecture Every graph with maximum degree $\Delta \geq 9$ has chromatic number at most $\max\{\Delta-1, \omega\}$....

Conjecture Every digraph has a stable set meeting all longest directed paths...

Conjecture There exists an ineteger $k$ so that every $k$-arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraph...

Conjecture Do any three longest paths in a connected graph have a vertex in common?...

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