143 problems

Let $G$ be a $2$-connected graph of order $n\ge 10$. Let $K_n$ denote the complete graph, and let $K_n^2$ and $K_n^{n-2}$ be the graphs obtained from $K_{n-1}$ by adding one vertex…

Let $G$ be a bipartite graph with $n$ vertices. The minimum distance signless Laplacian spread conjecture. … Equality holds if and only if … This proposes that the balanced complet…

Harary-polynomial comparability conjecture. Either $\chi_{\mathcal P}$ and $\chi_{\mathcal Q}$ are d.p.-equivalent or they are d.p.-incomparable.

Let $G$ be a connected graph, and let $\rho(G)$ denote its spectral radius, $d$ its degree vector, and $\operatorname{var}(G)$ its degree variance. Define the degree deviation by…

Let $G=(V,E)$ be a simple connected graph with $n=|V|$ vertices and $m=|E|$ edges. Its first and second Zagreb indices are … where $d_i$ is the degree of vertex $i$. Zagreb index i…

Lower-bound conjecture for tournament dijoins. One should have

Belkhechine et al.'s inversion-number conjecture.

Let $E_n$ be the degree anti-regular graph, meaning the unique connected graph whose vertex degrees attain every value from $1$ through $n-1$. Let $\omega(E_n)$ denote its minimum…

Let $G$ be an $n$-vertex graph, and let $wSz(G)$ denote its weighted Szeged index. Tree attainment conjecture. The minimum weighted Szeged index among $n$-vertex graphs is attained…

Let $\mathcal{B}'_n$ be the family of all bicyclic graphs on $n$ vertices, and let $G\in\mathcal{B}'_n$ have order $n\geq 8$. The Graovac-Ghorbani atom-bond connectivity index is d…

Let $G$ be a graph that is p-logarithmic in $d=4$ dimensions and whose vertices all have degree at most $4$; call such a graph a $\phi^4$ graph. Let $\mathcal{P}(G)$ denote its per…

Let $G$ be an $n$-vertex connected graph with chromatic number $\chi\geq 3$. For $t\geq 1$, let $T_{n,t}$ denote the complete $t$-partite graph of order $n$ whose partition sizes d…

Let $G$ be a connected graph with at least three vertices, let $P(G)$ denote its period, and let $c_2(G)$ denote its $c_2$-invariant. Period-$c_2$ invariance conjecture. For two pr…

Let $G$ be a finite, simple, connected bipartite graph with $n \geq 4$ vertices and $m \geq n$ edges. Its Wiener index is … and its Szeged index is … where $n_u(e)$ and $n_v(e)$ co…

Let $k\in\mathbb{N}$ and let $D_1,\dots,D_k$ be oriented graphs satisfying … Write $[D_1,\dots,D_k]$ for their join, and let $\operatorname{inv}$ denote inversion number. Dijoin co…

Vertex-deletion conjecture. There exists $v\in V(D)$ such that

Dijoin counterexample-range conjecture. For all $\ell,r\in\mathbb{N}$ with $\ell\geq 3$ or $r\geq 3$, there exist oriented graphs $L$ and $R$ such that

Dijoin conjecture.

Alon's inversion-number partition conjecture. For every two positive integers $k_1,k_2$, there exists an integer $f(k_1,k_2)$ such that every oriented graph $D$ with

Bang-Jensen et al.'s tightness conjecture. For every positive integer $n$, there exists an oriented graph $D$ such that

Let $G_1$ and $G_2$ be graphs with the same number of vertices, and let $\Delta$ be the dissimilarity measure obtained from the collections of horizontal homologies partitioned by t…

A graph's completion is the graph obtained by the completion operation referred to in the source, and $c_2$ denotes the $c_2$-invariant of a connected graph with at least three ver…

Asymptotic corank-growth conjecture. As $k\to\infty$,

Fixed-corank theta extremal conjecture. If $G\neq K_4$, then

Suppose that $\xi(G)$ is a 4-invariant of graphs extending the specialization of the $\mathfrak{sl}(2)$-weight system at $c=-\frac{3}{32}$. Let $G$ be a graph, let $x$ be a vertex…