13 problems

For a graph $G$, its square $G^2$ is the graph on $V(G)$ in which two vertices are adjacent when their distance in $G$ is at most two. Let $\chi$ and $\chi_\ell$ denote the chromat…

Let $G$ be a planar graph, and let $G^2$ denote its square, in which two vertices are adjacent when their distance in $G$ is at most two. Havet et al.'s conjecture. For any planar…

Let $G$ be a graph, and let $G^2$ denote its square. Write $chi(G^2)$ for the chromatic number of $G^2$ and $chi_{\ell}(G^2)$ for its list chromatic number, the least $k$ such that…

Let $G$ be a planar graph with girth $5$, let $\Delta$ denote its maximum degree, and let $M$ be a constant. The Dvořák conjecture. There exists some constant $M$ such that every p…

Let $G$ be a graph with maximum degree $k$. Write $G^2$ for the graph obtained by joining vertices of $G$ at distance at most $2$, let $w(G^2)$ denote the maximum clique size of…

Cubic bipartite planar square-coloring conjecture. The square satisfies

Let $G$ be a graph. Its square $G^2$ is obtained by joining distinct vertices that are connected by a two-edge path in $G$. Let $\operatorname{\Delta}(G)$ be the maximum degree,…

For each positive integer $k$, let $\alpha_k$ be the minimum value such that there is a constant $c_k$ with … whenever $G$ is $k$-degenerate and has maximum degree at most $D$. Let…

Let $G$ be a finite graph, and let $G^2$ denote its square, obtained by joining vertices at distance two as well as adjacent vertices. A graph is chromatic-choosable when its chrom…

Dvořák–Král'–Nejedlý–Škrekovski conjecture. If $\Delta(G)>M$, then

Dvořák–Král'–Nejedlý–Škrekovski conjecture. When $\Delta(G)$ is sufficiently large, one has

Gould–Jacobson conjecture. The connectivity condition in the assertion that the square of a 2-connected graph is Hamiltonian can be relaxed for $S(K_{1,3})$-free graphs; that is, e…

List-colouring extension of Wegner's conjecture.