An Approximate Algorithm for the Chromatic Number of Graphs

We have designed a novel polynomial-time approximate algorithm for the graph vertex colouring problem. Contrary to the common top-down strategy for solving the colouring graph problem, we propose a bottom-up algorithm for colouring graphs. Given an input graph G, we establish an upper bound to approximate the colouring of the input grap given by ⌈δ(G)/2⌉+2 where δ(G) is the average degree of G.