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.