Preface of David Cariolaro's thesis
Thousands of problems, many of which arise in the context of scheduling, job allocation, timetabling, marketing, finance, radio and TV-channel assignment, satellite communications, terrestrial, naval, air and space traffic control, can be reduced, ultimately, to graph-colouring problems.
Broadly speaking, we have a graph-colouring type of problem every time that our task is equivalent to the task of partitioning the elements of a graph (vertices, edges, regions, or any combination of these) according to a certain, distinguished, pre-defined criterion.
In this respect, the colours are simply labels, whose function is to mark the elements of the graph in such a way that the classes of the partition coincide with the classes of elements bearing the same colour (colour classes). The choice of the criterion by which the colours have to be allocated strictly depends on the problem at hand, but the most common criterion requires the colour classes to be independent, i.e. to contain no pair of mutually adjacent or incident elements.
Thus, for example, if the colouring affects only the vertices (edges) of the graph, and the criterion concerning the independence of the colour classes is observed, we obtain the ordinary concept of vertex-colouring (edge-colouring), whereas, if the colouring affects both vertices and edges, and the criterion concerning the independence of the colour classes is observed, we obtain the ordinary concept of total-colouring.
In this thesis the only type of colouring considered is edge-colouring. Edge-colouring problems arise naturally in a variety of contexts. An important subclass of edge-colouring problems which arise, e.g. in the context of scheduling, require that the colour classes of the colouring be 1-factors of the graph, i.e. that every vertex be incident with one edge of each colour class. These are usually called 1-factorization problems. The following example will help us to clarify the idea and give a quick overview of the main topics of the thesis.
Suppose that the director of a tennis tournament is about to design the time-table of the tournament. The tournament has 2n participants and, during each day of the competition, each of the 2n players must play exactly one game. There should be no player that, during any day of the tournament, does not play a match or plays more than one match, and no pair of players are allowed to play each other more than once during the tournament. Suppose, furthermore, that some of the players have already played each other previously during the season, and that, for some reasons, they cannot play each other during the tournament.
The director visualizes the situation by means of a graph G, with the 2n players as vertices, and with player x joined to player y by an edge if and only if x and y are allowed to play each other during the tournament. In order for the tournament to be played under the above conditions, and to last at least d days, each vertex of the graph has to have degree at least d. Assume, for simplicity, that each vertex of the graph has degree exactly d. Then the question "Can the tournament be scheduled in observance to the aforementioned rules?" is easily seen to be equivalent to the question "Is there an edge colouring of G using exactly d colours?", which is equivalent to the question "Is there a partition of the edge set of G into disjoint 1-factors?".
Sometimes the director will have to face the fact that the above problem has no solution. In this respect, dropping the condition "Player x cannot play player y more than once during the tournament" may be more desirable than dropping the condition "Every player must play one and only one game during each day of the tournament". In order to model this modified version of the problem, a new type of colouring, which we call excessive, needs to be introduced. Notice that, strictly speaking, this type of colouring problem is not a graph-colouring problem in the general sense specified above. Under this new type of "colouring", some (or possibly all) the edges of the graph are allowed to receive more than one colour, but every edge has to receive at least one colour.
Using this new concept, the tournament problem asks for the existence of an excessive edge-colouring in which each colour class forms a 1-factor, which we call an excessive 1-factorization. The duration of the tournament is now determined by the number of 1-factors in an excessive 1-factorization of G, which could be sensibly larger than the number d, common degree of the vertices of G. For example, for the Petersen graph, which is regular of degree 3, one can see that no less than five 1-factors are needed in an excessive 1-factorization, and five are sufficient.
In this thesis we shall address several questions concerning edge-colourings and 1-factorizations, and we shall introduce excessive 1-factorizations. All these concepts, and particularly the concept of excessive 1-factorization, seem to be open to the largest number of applications, for example in those areas where some unexpected and unwanted alterations of the scenario, such as system failure, delay, congestion, strike, market fluctuation, bad weather, cancellation or refund policy, malfunction, human error, must be taken into account.
JOC/EFR July 2015
The URL of this page is: