3319257285 by Unknown

Author:Unknown
Language: eng
Format: epub
Published: 2015-10-05T09:37:36+00:00

120

5 Applications and Extensions

In recent years, refinements to Haken and Appel’s proof have been made, with

Robertson et al. (1997) showing that, through various acts of trickery, only 633

configurations need to be considered. (A short summary of this proof, together with

a description of a polynomial-time algorithm for 4-colouring planar graphs, can

be found at http://people.math.gatech.edu/ ∼ thomas/FC/fourcolor.html.) However, a

proof along more “traditional” lines still remains elusive and, to this day, the Four

Colour Theorem remains an excellent example, along with Fermat’s Last Theorem,

of a problem that is very easy to state, but exceptionally difficult to prove.

Readers interested in finding out more about the fascinating history of the Four

Colour Theorem are invited to consult the very accessible book Four Colors Suffice:

How the Map Problem Was Solved by Wilson (2003).

5.2 Edge Colouring

Another way in which graphs might be coloured is by assigning colours to their

edges, as opposed to their vertices or faces. This gives rise to the edge colouring

problem where we seek to colour all edges of a graph so that no pair of edges

sharing a common vertex (incident edges) have the same colour, and so that the

number of colours used is minimal. The edge colouring problem has applications in

scheduling round robin tournaments and also transferring files in computer networks

(de Werra, 1988; Coffman et al., 1985). The minimum number of colours needed to

edge colour a graph G is called the chromatic index, denoted by χ( G). This should

not be confused with the chromatic number χ( G), which is the minimum number

of colours needed to vertex colour a graph G.

As mentioned earlier, the edge colouring and vertex colouring problems are very

closely related because we are able to edge colour any graph by simply vertex

colouring its corresponding line graph.

Definition 5.3 Given a graph G, the line graph of G, denoted by L( G) , is con-

structed by using each edge in G as a vertex in L( G) , and then connecting pairs

of vertices in L( G) if and only if the corresponding edges in G share a common

vertex as an endpoint.

An example conversion between a graph G and its line graph L( G) is shown in

Figure 5.6(a). From this process, it is natural that the number of vertices and edges

in L( G) is related to the number of vertices and edges in G.

Theorem 5.9 Let G = ( V, E) be a graph with n vertices and m edges. Then its line

graph L( G) has m vertices and

1 ∑ deg( v)2 −m

2 v∈V

edges.

5.2 Edge Colouring

121

v1

v2

v

(a)

1,v2

v1,v2

v3

4

v

4

v

,v

2 ,v

,v

2 ,v

v 1

5

v 1

5

v

v

v

v

4

5

4,v5

4,v5

G

L(G)

v

v

1,v2

1

v2

(b)

4

v

v

,v

2 ,v

3

v 1

5

v4,v5

v

v

L(G)

4

5

G

Fig. 5.6 Illustration of (a) how to convert a graph G into its line graph L( G), and (b) how a vertex

k-colouring of L( G) corresponds to an edge k-colouring of G

Proof. Since each edge in G corresponds to a vertex in L( G) it is obvious that L( G) has m vertices. Now let {u, v} be an edge in G. This means that {u, v} is a vertex in

L( G) with degree deg( u) + deg( v) − 2. Hence the total number of

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.