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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1016/j.endm.2014.08.013 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Graph Coloring,Approximate Algorithm,Chromatic Number | Discrete mathematics,Outerplanar graph,Combinatorics,Line graph,Graph power,Algorithm,Degree (graph theory),Petersen graph,Pathwidth,Windmill graph,Mathematics,Graph coloring | Journal |
Volume | ISSN | Citations |
46 | 1571-0653 | 1 |
PageRank | References | Authors |
0.63 | 1 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Guillermo De Ita Luna | 1 | 29 | 16.57 |
José Raymundo Marcial-Romero | 2 | 5 | 12.87 |
Yolanda Moyao | 3 | 1 | 2.32 |