10.2. Edge colouring.
Problem 2.: Each of n businessmen wishes to hold confidential meetings with some of the others. Assuming that each meeting lasts a day and at each meeting exactly two businessmen are present, in how many days can the meeting be over?
The corresponding graph-theoretical model: Let H be such a graph whose vertices correspond to the n businessmen and two vertices are adjacent iff the two businessmen wish to hold a meeting.
What is the minimal value of k for which can be partitioned into k classes, say
, such that
no two edges from the same class are adjecent?
A k-edge colouring C of a loopless graph G is an assignment of k colours, 1,2,...,k, to the edges of G. The colouring C is proper if no two adjacent edges have the same colour.
A proper k-edge colouring is a k-edge colouring in which each subset
is a matching.
A graph G is k-edge-colourable if G has a proper k-edge-colouring.
- Every loopless graph G is
-edge-colourable,
-
if G is k-edge-colourable, then G is also l-edge-colourable
for every
.
The (edge) chromatic number , of a
loopless graph G, is the minimum k for which G is k-edge-colourable. G is k-edge-chromatic if
.
The edge chromatic number of a graph G is
at least as large as the maximum degree .
The edge set of a bipartite graph can be partitioned into
classes of independent edges, so
.
What about the upper bounds?
Theorem 10.6.: .
Proof.
Each edge is adjacent to at most edges. Apply the result of the Theorem 9.9 we will get the desired
statement.
Theorem 10.7.: (Vizing): .
We omitt the proof.