10.1. Vertex colouring.
Problem 1: We wish to arrange the talks in a congress in such a way that no participant will be forced to miss a talk he would like to hear. Assuming a good supply of lecture rooms enabling us to hold as many parallel talks as we like, how long will the program have to last?
The corresponding graph-theoretical model: Let G be such a graph whose vertices are the talks and in which two talks are joined iff there is a particip-ant wishing to attend both.
What is the minimal value of k for which can be partitioned into k classes, say
such that no edge joins two vertices of the
same class?

Figure 10.1. A possible colouring of a graph G with 3 colours.
In a given colouring c of a graph G, a set consisting of all vertices assigned the same colour is referred to as a colour class:
.
We remark that we shall use real colours (red, blue, ...) only if there are few colours, otherwise the natural numbers will be our colours. Thus k-colouring of the vertices of G is a function
We denote the
minimal number of classes by
and call as the
(vertex) chromatic number of G.
If G is a graph for which
then G is k-chromatic.
For some graphs, the chromatic number is quiet easy to determine:
-
.
-
.
-
.
-
.
Some easy statement:
-
If a graph G does not
have an odd cycle then
.
-
If a graph G has an odd
cycle then
.
-
iff G is k-partite but G is not l-partite for
.
-
If
then
.
-
If G does not contain
independent edges then
Unfortunatelly, for we do not have a similar characterization of
graphs with chromatic number at least k, though there are some
complicated characterization.
Can we make a good characterization for k-chromatic graphs?
- The 1-chromatic graphs are the empty graphs.
- The 2-chromatic graphs are the nonempty bipartite graphs.
No value of is such an applicable characterization known.
The chromatic number of a disconnected graph is the maximum of the chromatic numbers of its components.
The chromatic number of a connected graph with cut-vertices is the maximum of the chromatic numbers of its blocks.
So, we will concern with determining the chromatic number of non-separable graphs; (i.e. graphs which do not have cut-vertices).
A graph G is k-(vertex) critical if and
for all
. (We
also say that G is critically k-chromatic.)
A graph G is k-(edge) critical if and
for all
. (We
also say that G is minimally k-chromatic.)
Every k-chromatic graph has a k-critical subgraph.
-
if
then the only 2-critical 2-chromatic graph is
, and
- the odd cycles are the only 3-critical 3-chromatic graphs.
For the k-critical graphs have not been
characterized, although it is quite difficult, in general, to determine whether
a given k-chromatic graph isk-critical or not.