EUVIMEDEUVIMED entdecken
Crossref

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

Døvling Andersen, Eric Mendelsohn

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →