演講訊息 TALKS

A 1-factorization of a (regular) graph is a decomposition of the edge set of the graph into disjoint 1-factors (perfect matchings). The problem of determining the existence of a 1-factorization and/or of explicitly nding a 1-factorization (if one exists) is an important problem in discrete mathematics, with several possible applications (e.g. scheduling, job assignment, etc.) The existence version of the problem is known to be NP-complete, even for 3-regular graphs. From the point of view of edge colouring, a 1 factorization of a graph G (if it exists) is nothing else than an optimal edge colouring of G, i.e. one which uses the minimum number of colours. In 1965 Vizing asked whether one can always obtain an optimal edge colouring of any graph starting from a non-optimal edge colouring and using only the technique of colour exchange, i.e. using only colour interchanges along maximal bicoloured paths or cycles until all unnecessary colours disappear. In this talk we shall give an answer to Vizing's question for all the regular graphs of small order (8 or less) by presenting a new technique (based on colour exchange) that allows one to obtain a 1-factorization of any 1-factorizable small graph in the way described above.