28 problems

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

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_{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…

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…

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…

Let $G$ be a graph with maximum degree $\Delta$, and let $\lambda^{2,1}(G)$ be the minimum span of an $L(2,1)$-labeling, in which vertices at distance one receive labels differing…

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 planar graph of girth at least $k$, and let $\Delta$ be its maximum degree. Wang–Lih conjecture. For every $k\ge 5$, there exists $\Delta_k$ such that, if…

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…

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

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 $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…

For a finite graph $G$, let $G^n$ be the graph with vertex set $V(G)^n$, in which two vertices are adjacent exactly when they differ in one coordinate and the entries in that coord…

De Joannis de Verclos–Kang–Pastor conjecture. For any claw-free graph $G$,

Let $G$ be a graph of maximum degree at most $d$, and let $G^t$ denote its $t$th power. Suppose that $G$ contains no cycle of length $2t+2$ as a subgraph. The $2t+2$-cycle conjectu…

Let $r$ and $k$ be integers with $r\geq k$. For a graph $G$ and a positive integer $l$, let $G^{(l)}$ be the graph on the same vertex set in which two vertices are adjacent when th…

Let $G$ be a graph on $n$ vertices. The square of a Hamiltonian cycle is $C_n^2$, where vertices at cyclic distance at most two are adjacent. Pósa's conjecture. If … then…

Let $G_{n,p}$ be the binomial random graph. The square of a Hamilton cycle is obtained from a Hamilton cycle by adding edges between all vertices at distance at most two on the cyc…

Cranston–Kim conjecture. If $G$ is not a Moore graph, then

Stronger finite-exception conjecture. For any $k\in\mathbb{N}^*$, except for a finite number of graphs, the $k$th power $G^k$ is $(D(k,\Delta)+1-k)$-choosable. This is posed as a s…

Let $G$ be a simple connected graph with maximum degree $\Delta\geq 3$. For $k\in\mathbb{N}^*$, let $G^k$ be the graph obtained by joining vertices at distance at most $k$, and def…

Let $k$ and $r$ be positive integers. The problem textsc{$k^{th}$Power of a Graph With Girth $r$} asks, given a graph $G$, whether there exists a graph $H$ of girth $r$ such that…