210 problems

Lower-bound conjecture for tournament dijoins. One should have

Let $G=(V,E)$ be a finite tree. Its generalized degree polynomial (GDP) is … where $\operatorname{ext}(A)$ is the number of edges of $E$ with one endpoint in $A$, and…

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…

For a $phi^4$ graph $G$, let $P_G$ denote its Feynman period and let $H_G$ denote its Hepp bound, a combinatorial invariant of $G$. Panzer's Hepp-bound conjecture. Two $phi^4$ grap…

Let $G$ be a triangle-free graph on $n$ vertices. The balanced complete bipartite graph conjecture. Among triangle-free graphs on $n$ vertices, the maximum value of the subpath num…

Let $G$ be a connected graph with $n(G)\geq 3$. Write $\alpha(G)$ for its independence number, $\Delta(G)$ for its maximum degree, $a(G)$ for its annihilation number, and…

Mostar index extremal graph conjecture. For any $n \ge 3$, the graph

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…

Martin-sequence conjecture. The Martin sequence $\operatorname{\mathsf{M}}(G^\bullet)$ determines the value of $\mathsf{N}_2(G)$.

Let $G$ be a graph. The parameters $Z(G)$ and $Z_+(G)$ denote the standard and positive semidefinite zero forcing numbers of $G$, respectively. A graph is claw-free if it has no in…

Let $D$ be a digraph, and let $\rho(D)$ and $\pi(D)$ denote its remoteness and proximity, respectively. Regularity conjecture. If … then $D$ is regular. The preceding result proves…

Kotlov–Lovász–Vempala conjecture. For every such graph $G$,

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 of size $m$, and let $es_g(G)$ denote its group edge irregularity strength, the least order of an Abelian group for which $G$ admits an edge-irregular labeling b…

Brown–Schnetz conjecture. For every prime $p$,

G-degree and generalized gem-complexity conjecture. One has

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…

Frustration equality conjecture. For every signed cubic graph $\Sigma$,

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 $G$ be a graph with minimum degree $\delta(G)$, and let $\nu(G)$ denote its Colin de Verdière parameter, defined as the maximum nullity among positive semidefinite matrices ass…

Let $G$ be a finite group, and let ${\frak D}(G)$ denote its division graph, a disjoint union of finitely many connected, directed, vertex-colored, and arc-labeled graphs obtained…

Let $c>1$ be a constant, let $p=\frac{c}{n}$, and let $G$ be the giant component of a random graph ${\cal C}G(n,p)$. Here $D(G)$ denotes the distinguishing number of $G$, and “with…

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

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