47 problems

Seymour's conjecture. For positive integers $n$ and $k$ with $n\geq k+1$ and $k\geq2$, if

Let $G_{n,p}$ be the random graph on $n$ vertices, let $G_{n,p}^r$ denote its $r$th power, and write $\chi(G)$ and $\alpha(G)$ for the chromatic and independence numbers of a graph…

Let $G$ be a graph on $n\geq 3$ vertices, let $r$ be a positive integer, and let $\delta(G)$ denote the minimum degree of $G$. The $r$-th power $\mathcal{C}^r$ of a Hamilton cycle…

For a finite simple graph $G$, let $L(G)$ denote its line graph, let $G^2$ denote the graph in which two vertices are adjacent exactly when they are at distance at most two in $G$,…

Let $G$ be a connected graph with maximum degree $\Delta\ge 3$, and let $G^2$ be its square. Cranston–Kim conjecture. If … then … This strengthens the known exceptional behavior at…

Path-power equitable list arboricity conjecture. The graph $G$ is equitably $k$-list arborable if and only if

Let $G$ be a graph, and let $G^2$ denote its square, with two vertices adjacent whenever their distance in $G$ is at most $2$. Write $\chi$ for chromatic number and $\chi_\ell$ for…

Let $G$ be a planar graph of girth at least $5$, and let $\Delta$ be its maximum degree. Dvořák–Kráľ–Nejedlý–Škrekovski conjecture. There exists $\Delta_0$ such that, if…

Let $G$ be a graph, let $\Delta(G)$ denote its maximum degree, let $\operatorname{mad}(G)$ denote its maximum average degree, and let $G^2$ be its square, with chromatic number…

Let $G$ be a chordal graph, meaning that every cycle of length at least four has a chord. For an integer $k\geq1$, let $G^k$ be the $k$th graph power, in which two vertices are adj…

Independence-growth conjecture. For every integer $n\geq 4$,

Fix integers $k\geq2$ and $m\geq k+1$. Let $P$ be an $m$-path whose vertex set is partitioned as … For a vertex subset $V_j$, write $P[V_j]$ for the induced subgraph, and let…

Mozafari-Nia–Iradmusa conjecture. For every simple graph $G$,

Total colouring conjecture. For every simple graph $G$,

Let $G$ be a graph, let $G^2$ denote its square, let $\Delta(G)$ be its maximum degree, let $\chi(G^2)$ be the chromatic number of $G^2$, and let $\operatorname{mad}(G)$ be its max…

Let $G$ be a square graph, meaning a graph of the form $H^2$ for some graph $H$, and let $\Delta(G)$ denote its maximum degree. Write $\chi$ for chromatic number and $\chi_\ell$ fo…

For integers $k,r\geq 1$, let $f(k,r)$ be the smallest integer such that every $k$-connected graph $G$ whose order is divisible by $r$ has a $K_r$-factor in $G^{f(k,r)}$. The 3-con…

Let $r\geq 2$ be an integer, and let $G$ be a 2-connected graph whose order is divisible by $r$. A $K_r$-factor is a spanning subgraph whose components are copies of the complete g…

A graph class $\mathcal{G}$ is nice if it is minor-closed and does not contain $K_{3,t}$ for some positive integer $t$. Havet–van den Heuvel–McDiarmid–Reed conjecture. There exists…

Let $G$ be a planar graph. Havet–van den Heuvel–McDiarmid–Reed conjecture. … The conjecture was disproved in 2022 by Hasanvand, although it remains open for graphs with maximum deg…

Xiao–Katona–Xiao–Zamora conjecture. For the square of the path $P_k$, one has

Bonamy–Bousquet's conjecture. For every $k\geqslant 2$, only finitely many graphs $G$ satisfy

Let $P_k$ be the path on $k$ vertices, let $P_k^2$ denote its square, and let ${\rm ex}(n,P_k^2)$ be the maximum number of edges in an $n$-vertex graph containing no copy of…

Let $P_k$ be the path on $k$ vertices, let $P_k^2$ denote its square, and let ${\rm ex}(n,P_k^2)$ be the maximum number of edges in an $n$-vertex graph containing no copy of…

Higher power adjoint conjecture. For graphs $G$ of girth greater than $4k$,