10.1.2. Upper bounds for the vertex chromatic number

It is not to hard to improve the efficiency of the greedy algorithm:

If we already know a subgraph which can be coloured with few colours, , then we may start our sequence with the vertices of , colour in an efficient way and apply only then the algorithm to colour the remaining vertices.

Theorem 10.1.: Let be a spanned subgraph of G and suppose every subgraph H satisfying contains a vertex . Then

Proof.

It is trivial. The only thing we need to do is to give the vertices in the appropriate order.

Theorem 10.2.: Let , where the maximum is taken over all spanned subgraphs of G. Then .

Proof.

Let a vertex with , and let

By assumption has a vertex of degree at most k.

Let be one of them and put .

Continuing in this way we enumerate all vertices.

The sequence is such that each xj  is joined to at most k vertices preceding it. Hence the greedy algorithm will never need colour to colour a vertex.

Consequence 10.3.: , where is the maximum degree of G.

This follows immediately from the fact that .

Consequence 10.4.: If G is connected and not -regular then clearly , and so .