Contents

Utilitas Mathematica

  • Research article

Avoiding 2-coloured 4-cycles in edge-coloured subcubic bipartite graphs

Lars Døvling Andersen1, Eric Mendelsohn2
1Department of Mathematical Sciences, Aalborg University, Thomas Manns Vej 23, DK-9220 Aalborg Ø, Denmark
2Department of Mathematics, University of Toronto, 40 St. George St., Toronto, ON M5S 2E4, Canada
  • Received: 04/03/2026
  • Revised: 01/04/2026
  • Accepted: 03/04/2026
  • Published Online: 06/05/2026

Abstract

There are a number of variations of proper edge-colourings of graphs with restrictions on the subgraphs induced by two colour classes. Deciding whether a graph has a 3-edge-colouring with no 2-coloured 4-cycle is NP-complete for cubic graphs with chromatic index 3. But for bipartite cubic graphs the problem is solved completely in this paper. Furthermore, the minimum number of 2-coloured 4-cycles in a 3-edge-colouring is determined for any subcubic bipartite multigraph.

Keywords: soft set theory, symmetric difference operations, algebraic structures
Citation
Lars Døvling Andersen, Eric Mendelsohn. Avoiding 2-coloured 4-cycles in edge-coloured subcubic bipartite graphs[J], Utilitas Mathematica, Volume 127. 75-92. https://doi.org/10.61091/um127-05.