Edge colourings of multigraphs [Elektronische Ressource] / von Diego Scheide

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_ilmenau
• Publié le: 01 janvier 2009
• Nombre de lectures: 53
• Langue: Deutsch
• Poids de l'ouvrage: 2 Mo

Extrait

Edge Colourings of Multigraphs
Dissertation
zur Erlangung des akademischen Grades
doctor rerum naturalium (Dr. rer. nat.)
vorgelegt der Fakultät für Mathematik und Naturwissenschaften
der Technischen Universität Ilmenau
von Dipl.-Math. Diego Scheide
1. Gutachter: Prof. Dr. rer. nat. habil. Michael Stiebitz
2.hter: Dr. habil. Reinhard Diestel
3. Gutachter: Prof. RNDr. Jan Kratochvil
Tag der Einreichung: 21.10.2008
Tag der wissenschaftlichen Aussprache: 27.02.2009
urn:nbn:de:gbv:ilm1-2009000218Contents
1 Introduction 1
1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Edge Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Critical Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Elementary Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Edge Colouring Algorithms 7
2.1 How to Colour a Graph? . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 The Vizing Fan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 The Fan Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 The Kierstead Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.6 The Tashkinov Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.7 A New Upper Bound for the Chromatic Index . . . . . . . . . . . . . 43
3 Goldberg’s Conjecture 56
3.1 On the 15/14 Edge Colouring of Graphs . . . . . . . . . . . . . . . . 56
3.2 Tashkinov Trees in Critical Graphs . . . . . . . . . . . . . . . . . . . 58
3.3 Balanced Tashkinov Trees . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4 The Main Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.5 Proof of Theorem 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.6 Some Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4 Polynomial-Time Algorithms 91
4.1 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2 Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.3 A Polynomial Time Colouring Scheme . . . . . . . . . . . . . . . . . 103
References 105
Index 108
Symbols 110
i1 Introduction
The Edge Colouring Problem (ECP) is to find the chromatic index of a given graph
G, that is, the minimum number of colours needed to colour the edges of G such
that no two adjacent edges receive the same colour. Edge colouring problems occur
in various scheduling applications, typically in conjunction with task processing or
network communication, minimizing the number of time-slots needed for completing
a given set of tasks or data transfers. Good scheduling algorithms become more and
more important, e.g., due to the increased use of multiprocessor environments or the
increasing complexity in the wide field of logistics. Most papers on edge colouring
deal mainly with edge colourings of simple graphs. In many scheduling problems,
however, (multi)graphs occur in a natural way, and (multi)graph edge colouring is
a topic where further work should be done. One of the major unsolved problems in
this area is Goldberg’s conjecture (see. Section 1.4).
0Goldberg suggested an upper bound for the chromatic index ´ in terms of the
0maximum degree ¢ and the density W, namely ´ • maxf¢+1;Wg. Since ¢ is a
0lower bound for the chromatic index, Goldberg’s conjecture implies that ´ is equal
to ¢, or to ¢+1, or to W.
Upper bounds for the chromatic index of a graph come often from algorithms
that produce edge colourings. As discussed in Chapter 2, a typical algorithm colours
the edges of an input graph sequentially, that is, the edges are coloured one at a time
with respect to a given edge order. The core of such an algorithm is a subroutine that
extends a given partial colouring of the input graph to the next uncoloured edge. In
each call of the subroutine, we have to decide whether we will use a fresh colour or
not. To make this decision, we shall use so-called test objects. A classical kind of test
objects, called Vizing fans, was introduced by Vizing [39] in 1964. Vizing used these
0test objects to establish an upper bound for the chromatic index ´ in terms of the
0maximum degree ¢ and the maximum multiplicity „, namely ´ • ¢+„. Vizing’s
bound is rather generous. In most graphs there will be scope for an improvement
of Vizing’s bound by choosing a suitable edge order to start with. This leads to a
new graph parameter, the fan number. The fan number, introduced in Section 2.4,
resembles the colouring number, and seems to be the best upper bound for the
chromatic index that can be obtained by the fan argument. Another type of test
objects, called Kierstead paths, was introduced by Kierstead [19] in 1984. Recently,
Tashkinov [38] obtained a common generalization, Tashkinov trees, of the Vizing
fans and the Kierstead paths, see Section 2.6. As we shall see in Section 2.7, some
new upper bounds for the chromatic index in terms of the maximum degree ¢ and
the density W can be obtained from Tashkinov methods. These results generalize
an earlier result of Kahn [18] proved by probabilistic methods, and improve earlier
0bounds for ´ by Sanders and Steurer [25].
In Chapter 3 we extend an earlier result of Favrholdt, Stiebitz and Toft [8], and
0 15 12show that ´ •maxf ¢+ ;Wg. The proof of this result is based on an extension14 14
of Tashkinov’s methods. The results of Chapter 3 imply that Goldberg’s conjecture
holds for all graphs with at most 15 vertices as well as for all graphs with maximum
degree at most 15. If Goldberg’s conjecture is true, we can also give a complete
answer to the following natural question. For which value of ¢ and „ does there
10exist a graph G satisfying ¢(G)=¢, „(G)=„, and ´(G)=¢+„?
All colouring algorithms presented in the first three chapters have execution time
polynomial in jEj and jVj, but are only pseudo-polynomial in the number of bits
needed to describe the graph G=(V;E), since the size of the input graph G may be
of orderlogjEj. In Chapter 4 we use ideas from Sanders and Steurer [25] to develop a
scheme for polynomial-time edge colouring algorithms that can realize several upper
bounds of the chromatic index.
1.1 Graphs
By a graph we mean a finite undirected graph without loops, but possibly with
multiple edges. The vertex set and the edge set of a graph G are denoted by
V(G) and E(G), respectively. For a vertex x 2 V(G), let E (x) denote the setG
of all edges of G that are incident with x. Two distinct edges of G incident to the
same vertex will be called adjacent edges. Furthermore, for X;Y ? V(G), let
E (X;Y) denote the set of all edges of G joining a vertex of X with a vertex of Y.G
We write E (x;y) instead of E (fxg;fyg). Two distinct vertices x;y 2 V(G) withG G
E (x;y) =; will be called adjacent vertices or neighbours. Let N (x) denoteG G
the set of all neighbours of x in G, that is, N (x)=fy2V(G)jE (x;y)=;g.G G
The degree of a vertex x 2 V(G) is d (x) = jE (x)j, and the multiplicityG G
of two distinct vertices x;y 2 V(G) is „ (x;y) = jE (x;y)j. Let –(G), ¢(G)G G
and „(G) denote the minimum degree, maximum degree and the maximum
multiplicity of G, respectively. A graph G is called simple if „(G)• 1. A graph
G is called regular or r-regular if d (x) = r for every vertex x of G, where r‚ 0G
is an integer.
For H is a subgraph of G, we write briefly H ? G. For a graph G and a set
X ?V(G), letG[X]denotethesubgraphofGinducedbyX, thatis,V(G[X])=X
and E(G[X])=E (X;X). Further, letG¡X =G[V(G)nX]. We also write G¡xG
instead ofG¡fxg. ForF ?E(G), letG¡F denote the subgraphH ofG satisfying
V(H) = V(G) and E(H) = E(G)nF. If F = feg is a singleton, we write G¡e
rather than G¡feg. For the graph H = G¡e, we further define H +e to be the
graph G.
The line graph of G, denoted by L(G), is the simple graph defined as follows.
The vertex set V(L(G)) equals the edge set of G, and between two vertices e;f 2
V(L(G)) there is an edge iff e and f are adjacent edges in G.
If S is a sequence consisting of edges and vertices of a given graph G, then
we denote by V(S), respectively E(S), the set of all elements of V(G), respec-
tively E(G), that belong to the sequence S. Let G be a graph, and let S =
(v ;e ;v ;:::;v ;e ;v ) be a such that v ;:::;v are distinct vertices0 1 1 p¡1 p p 0 p
of G, and e ;:::;e are edges of G. For a vertex v 2 V(S), we define Sv =1 p i i
(v ;e ;:::;e ;v ) andv S =(v ;e ;:::;v ).0 1 i i i i i+1 p
By a path, a cycle, or a tree we usually mean a graph or subgraph rather than a
sequence consisting of edges and vertices. The only exceptions will be the Kierstead
path and the Tashkinov tree, we consider both as sequences. If P is a path of length
p‚0 with V(P)=fv ;:::;v g and E(P)=fe ;:::;e g such that e 2E (v ;v )0 p 1 p i P i¡1 i
for i = 1;:::;p, then we also write P = P(v ;e ;v ;:::;e ;v ). Clearly, the0 1 1 p p
2
66vertices v ;:::;v are distinct, and we say that v and v are the endvertices of P0 p 0 p
or that P is a path joining v and v . For x;y2V(P), the subpath of P joining x0 p
and y is denoted byxPy oryPx. If u is an endvertex of P, then we obtain a linear
order