| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4651838 | Electronic Notes in Discrete Mathematics | 2014 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
