Colourfully Panconnected Subgraphs \(II\)

Abstract

Let \(G\) be a connected \(k\)-colourable graph of order \(n \geq 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 \geq 4\) and \(G\) is not a circuit (a connected \(2\)-regular graph) with length \(\equiv 1 \pmod{k}\). It is proved that \(s_k(G) = n-1\) if \(G\) contains no circuit with length \(\equiv 1 \pmod{k}\), and \(s_k(G) \leq 2n-k-1\) whenever \(k \geq 4\).