Two results on rich-neighbour $5$-colouring of subcubic graphs
A rich-neighbour edge-colouring is a proper edge-colouring in which every non-isolated edge has an adjacent edge whose neighbours have pairwise distinct colours. Petruševski and Škrekovski conjectured that every connected subcubic loopless multigraph distinct from $K_4$ admits such a colouring with five colours. We prove the conjecture for two classes: claw-free subcubic loopless multigraphs and $2$-connected subcubic outerplanar loopless multigraphs. The bound is sharp in both classes, as witnessed by the diamond $K_4-e$.
Authors
- Mirko Petruševski (ORCID: https://orcid.org/0000-0001-8048-7418)
- Masaki Kashima (ORCID: https://orcid.org/0009-0006-8710-169X)
- Riste Škrekovski (ORCID: https://orcid.org/0000-0001-6851-3214)
- Jelena Sedlar (ORCID: https://orcid.org/0000-0002-8973-5163)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.24297
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- preprint