Ordered colourings of graphs

An ordered colouring of a graph with k colours is a vertex colouring with colours {1, 2,…,k} such that each vertex coloured j is joined to at least one vertex-of colour i for each i less than j. Examples of ordered colourings are those produced by the greedy colouring algorithm. Some properties are investigated of τ(G), the maximum k for which the graph G has an ordered k-colouring (in fact τ(G) is an upper bound for the number of colours used by the greedy algorithm). It is shown that if G has order n, then $\text{τ(G) + τ(}\text{G}\text{) ≤ [}\text{(5n + 2)}\text{4}\text{]}$.