Paperlane

no. 14 · Friday 13 November 2026

Strong edge-colourings of truncations of cubic graphs

Domenico Labbate and Federico Romaniello

math.CO · v2 · 23 pp

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
pdf ↗ page arXiv:2610.41950 ↗