The objective function is given to us - we want to minimize the number of colours used.

We can structure the problem as a sequence of decisions in at least two ways:
    1. Put the vertices in some order: v1, v2, ..., vn
          At stage i of the algorithm, choose a colour for vi
    2. Assign numbers to the colours 1, 2, ... n      (note that we will never need more than n colours)
          At stage i of  the algorithm, choose vertices to colour with colour i

Let's explore method 1.

Global upper bound U - as noted, we never need more than n colours.  We can use n as the initial value of U

Lower bound function:  Let S be a partial solution, in which we have assigned colours to vertices 1, 2, ..., i.  Our lower bound on the best possible solution obtainable from S must obviously include the number of colours used so far ... can we do better?  Maybe.  We can scan the vertices not yet coloured.  If any of them are adjacent to vertices covering the full set of colours used so far, then we will need at least one more colour.  If any such vertices are also ajacent to each other, we will need at least two more colours.  This test would take O(n^2) time, but since we are doomed to exponential time in the worst case anyway, spending O(n^2) to help reduce the tree is probably worthwhile.

So we can define L(S) = "number of colours used so far" + "number of colours we will be forced to use in the future"

Remember that the second part of L(S) doesn't have to be exact - but it must be a true lower bound.  That is, if it is not exact it must be less than the exact value.


Upper bound function:  Let S be a partial solution, in which we have assigned colours to vertices 1, 2, ..., i.  As a simple upper bound on the number of colours used in the best solution obtainable from S, we could use U(S) = "number of colours used so far" + "number of vertices not yet coloured", since the worst thing that could happen is that each remaining vertex needs its own colour.  However, we can try to do better.  If we apply any kind of heuristic (such a Greedy-style heuristic based on "for each remaining vertex, choose the legal colour that has been used the most often (note that the legal colours for each vertex may change as we go along)") we have a chance of arriving at a solution that uses close to the optimal number of colours.  If we are fortunate, this will give us a relatively tight upper bound on the optimal solution.

So we can define U(S) = "number of colours used so far" + "number of colours used to colour the remaining vertices by applying the Greedy heuristic"

We are done.


Note: there are many other heuristics that could be applied instead of the simplistic Greedy one described above.  For example, we could randomly pick a colour for each remaining vertex (making sure the colouring is legal after each pick).  Or we can pick a colour for whichever remaining vertex is adjacent to the most different colours among the vertices v1, ... vi (this makes sense in a way because this vertex is the most tightly constrained as to potential colours), and then repeat until we have coloured all the vertices.  As long as we follow some procedure to arrive at a valid (not necessarily optimal) solution, we will be finding a valid upper bound on the cost of the optimal solution obtainable from S.