Colourfully Panconnected Subgraphs $II$

Abstract

Let $G$ be a connected $k$-colourable graph of order $n\ge k$. A subgraph $H$ of $G$ is $k$-colourfully panconnected in $G$ if there is a $k$-colouring of $G$ such that the colours are close together in $H$, in two different senses (called variegated and panconnected) to be made precise. Let $s_k(G)$ denote the smallest number of edges in a spanning $k$-colourfully panconnected subgraph $H$ of $G$. It is conjectured that $s_k(G)=n-1$ if $k\ge 4$ and $G$ is not a circuit (a connected $2$-regular graph) with length $\equiv 1(\mathrm{mod}k)$. It is proved that $s_k(G)=n-1$ if $G$ contains no circuit with length $\equiv 1(\mathrm{mod}k)$, and $s_k(G)\le 2n-k-1$ whenever $k\ge 4$.