Delay colourings of cubic graphs

MaRDI QIDQ396884zbMATH OpenFDO

Authors Agelos Georgakopoulos

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.1306, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p45

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

cubic graphedge colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this note we prove the conjecture of cite{HaWiWi} that every bipartite multigraph with integer edge delays admits an edge colouring with $d+1$ colours in the special case where $d=3$. A connection to the Brualdi-Ryser-Stein conjecture is discussed.

Review text

Summary: In this note we prove the conjecture of \textit{G. T. Wilfong} et al. [``Delay coloring and optical networks, Preprint (2001)] that every bipartite multi-graph with integer edge delays admits an edge colouring with \(d+1\) colours in the special case when \(d = 3\).

Recommendations

• Edge Colouring with Delays
• Delay colouring in quartic graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• Proof of Melnikov-Vizing conjecture for multigraphs with maximum degree at most \(3\)

Cites work

• A Combinatorial Problem on Abelian Groups
• Combinatorial matrix theory
• Edge Colouring with Delays
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Rainbow matchings in r-partite r-graphs
• Transversals of latin squares and their generalizations

Cited in

(3)

• Edge Colouring with Delays
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Delay colouring in quartic graphs

This page was built for publication: Delay colourings of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396884)