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
.