85 problems

Haemers' conjecture. The fraction of graphs on $n$ vertices with an $M$-cospectral mate tends to zero as $n$ tends to infinity.

Let $G$ be a finite simple undirected graph. Its $1$-vertex deck is the multiset of isomorphism types of the graphs obtained by deleting one vertex from $G$. The Reconstruction Con…

Hamiltonian path pattern conjecture. In order for a Hamiltonian path to exist on $I[G]$, it is necessary and sufficient that $I[G]$ satisfy one of the four possible patterns:

Let a graph be determined by its adjacency spectrum if every graph with the same adjacency eigenvalue multiset is isomorphic to it. Van Dam–Haemers conjecture. Almost all graphs ar…

Let $\mathcal{M}$ be a graph class that is proper, minor-closed, and union-closed. For graphs $G$ and $H$, write $G =_{\mathcal{M}} H$ when $\hom(K,G)=\hom(K,H)$ for every…

Let $G$ and $H$ be trees, and let $\chi_G(x)$ denote the chromatic symmetric function of $G$. Tree isomorphism conjecture. If $G$ and $H$ are non-isomorphic trees, then … The conje…

Cameron–Ghosh conjecture. If the power graphs of $G$ and $H$ are isomorphic, then $G$ and $H$ have the same number of elements of each order.

Let $G$ and $H$ be graphs, and let $\operatorname{RS}(G)$ denote the multiset of resistance distances between all pairs of distinct vertices of $G$. Baxter's conjecture. Two graphs…

Let $D(q;m,n)=D_2(\mathbb F_q;X^mY^n)$ be a monomial digraph over the field with $q$ elements. Kodess's conjecture. For a prime power $q$, the digraphs $D(q;m_1,n_1)$ and…

Let $G$ and $H$ be graphs. Their distance degree sequences are the vectors formed by the transmissions of their vertices. Randić's conjecture. The graphs $G$ and $H$ are isomorphic…

Stanley’s tree isomorphism conjecture. The chromatic symmetric function distinguishes trees: if $T$ and $T'$ are trees and $X_T=X_{T'}$, then $T$ and $T'$ are isomorphic.

Emms–Hancock–Severini–Wilson conjecture.

Let $Y(g,k)$ be a Young graph, and let $Z_m$ denote the equivalence class of cyclic Young graphs on $m$ nodes. Cyclic Young graph conjecture. For $t\ge 3$ and $n\ge 2$, the Young g…

Loebl's conjectures. The q-dichromate is equivalent to the U-polynomial, and the q-dichromate distinguishes non-isomorphic chordal graphs. Equivalently, in the latter assertion, eq…

Let $k$ be a positive integer, let $c$ be the multiplicative order, and let $w_1,w_2$ be units modulo $k$. For each unit $w$, let $G(k,c,w)$ denote the corresponding metacyclic cen…

The New Digraph Reconstruction Conjecture. The source proposes a directed reconstruction conjecture based on the collection of these triples, asserting that this augmented vertex-d…

Let $G$ be a finite simple undirected graph. Its $1$-edge deck is the multiset of isomorphism types of the graphs obtained by deleting one edge from $G$. The Edge-Reconstruction Co…

Subtree separation conjecture. The universal support-forest-counting combinations arising from $M_r^{(2)}(T)$, together with the Laplacian spectrum, determine all embedded forest c…

Spectral support-forest-profile conjecture. If $T_1$ and $T_2$ have the same Laplacian spectrum and the same $(n-2,2)$ support-forest profile, then $T_1$ and $T_2$ are isomorphic.…

Lifting conjecture. Then, for some $S$,

Let $C_{n_1}(R_1)$ and $C_{n_2}(R_2)$ be circulant graphs such that … for some $R$. Product criterion conjecture. The graph $C_{n_1n_2}(R)$ has Type-2 isomorphic circulant graphs i…

Let $\mathcal{M}_1$ and $\mathcal{M}_2$ be two distinct immersion-closed and union-closed graph classes. For graphs $G$ and $H$, write $G =_{\mathcal{M}} H$ when…

For a graph $G$, its Hadwiger number is the largest integer $t$ such that $G$ contains the complete graph $K_t$ as a minor. Two graphs are homomorphism indistinguishable over a gra…

Let $G$ be a graph, and let $fbar{X}_G$ denote its Kromatic symmetric function. Two graphs are isomorphic when they differ only by a relabeling of their vertices. Pierson's conject…

Let $G,H,G_a,G_b$ be graphs, let $E_G\subset E(G)$ and $E_H\subset E(H)$ be edge subsets, let $T_a,T_b$ be spanning trees, and let $S_G\in V(G)\cup E(G)$ and $S_H\in V(H)\cup E(H)$…