Premium
1‐factorization of regular graphs by colour exchange
Author(s) -
Cariolaro David
Publication year - 2008
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/jdm117
Subject(s) - conjecture , mathematics , combinatorics , multigraph , edge coloring , factorization , graph , class (philosophy) , enhanced data rates for gsm evolution , discrete mathematics , graph theory , computer science , line graph , algorithm , artificial intelligence , graph power
We present a new general theory that deals with the problem of determining a 1‐factorization of a graph using only the elementary technique of colour exchange. Our work is inspired by an old question of Vizing, who in [ Cybernetics 3 (1965) 32–41] asked whether an optimal edge colouring of any multigraph G can always be obtained from an arbitrary edge colouring of G by repeatedly exchanging colours along bicoloured chains and suppressing empty colour classes. We conjecture that the answer to Vizing's question is affirmative. We apply our theory to the class of regular graphs of even order at most 10, proving the validity of this conjecture for this class of graphs. This yields an algorithm for finding a 1‐factorization of any 1‐factorizable graph of order at most 10. We also formulate two (stronger) conjectures and prove that they hold for the same class of graphs. Our method can be extended to graphs of larger order and to non‐regular graphs or multigraphs.