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.