Avoiding 2-coloured 4-cycles in edge-coloured subcubic bipartite graphs Lars
Utilitas Mathematica · 10.05.2026 · 127 · 75-92
DOI: 10.61091/um127-05 ↗Kurz gefasst
Fachartikel in der Zeitschrift Utilitas Mathematica, online erschienen am 10.05.2026. Verfasst von Døvling Andersen und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Andersen, D., & Mendelsohn, E. (2026). Avoiding 2-coloured 4-cycles in edge-coloured subcubic bipartite graphs Lars. Utilitas Mathematica, 127, 75-92. https://doi.org/10.61091/um127-05
Vancouver
Andersen D, Mendelsohn E. Avoiding 2-coloured 4-cycles in edge-coloured subcubic bipartite graphs Lars. Utilitas Mathematica. 2026;127:75-92. doi:10.61091/um127-05
BibTeX
@article{Andersen2026,
author = {Andersen, Døvling and Mendelsohn, Eric},
title = {Avoiding 2-coloured 4-cycles in edge-coloured subcubic bipartite graphs Lars},
journal = {Utilitas Mathematica},
year = {2026},
volume = {127},
pages = {75--92},
doi = {10.61091/um127-05}
}
EUVIMED