no. 14 · Friday 13 November 2026
Strong edge-colourings of truncations of cubic graphs
Abstract
We study a problem posed by Kardoš asking whether the truncation of every connected simple bridgeless cubic graph has strong chromatic index six. The truncation $T(G)$ is obtained by replacing each vertex of a graph $G$ with a triangle and attaching its three incident edges to distinct vertices of that triangle. Han and Cui established an affirmative answer for prism bases. We prove that the strong chromatic index is six whenever $G$ is a connected simple cubic graph that is bipartite or is both bridgeless and claw-free. Both proofs are constructive and use a common compatibility criterion for combining colourings of smaller pieces. The same equality holds for connected loopless cubic multigraphs in either class, with the sole exception of the $3$-bond, whose truncation is the triangular prism and has strong chromatic index nine.
- comments
- 23 pages, 5 figures, 7 tables
- fields
- Combinatorics