Creator:

Formanowicz, Piotr ; Tanaś, Krzysztof

Contributor:

Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.

Title:

The Fan-Raspaud conjecture: a randomized algorithmic approach and application to the pair assignment problem in cubic networks

Group publication title:

AMCS, Volume 22 (2012)

Subject and Keywords:

cubic graph ; edge coloring ; perfect matching ; randomized algorithms ; computer networks

Abstract:

It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs ; The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another possible application of the algorithms is that of being a tool for mathematicians working in the field of cubic graph theory, for discovering edge colorings with certain mathematical properties and formulating new conjectures related to the Fan-Raspaud conjecture.

Publisher:

Zielona Góra: Uniwersytet Zielonogórski

Date:

2012

Resource Type:

artykuł

DOI:

10.2478/v10006-012-0057-y

Pages:

765-778

Source:

AMCS, Volume 22, Number 3 (2012) ; click here to follow the link

Language:

eng

License CC BY 4.0:

click here to follow the link

Rights:

Biblioteka Uniwersytetu Zielonogórskiego