Graph Coloring Using Eigenvalue Decomposition
Copyright policy )Graph Coloring Using Eigenvalue Decomposition
A heuristic algorithm for proper vertex colouring of a graph which is based on eigenvectors of the adjacency matrix is proposed in this paper. Signs of coordinates of the eigenvector belonging to the least eigenvalue determine a 2-colouring. This colouring is refined using gradually other eigenvectors in a similar way. It is conjectured that eigenvectors belonging to negative eigenvalues are sufficient to obtain a proper colouring. For some classes of graphs the colouring obtained has a reasonably small number of colours.
Coloring of graphs and hypergraphs, Graphs and linear algebra (matrices, eigenvalues, etc.), eigenvectors of the adjacency matrix, vertex colouring
Coloring of graphs and hypergraphs, Graphs and linear algebra (matrices, eigenvalues, etc.), eigenvectors of the adjacency matrix, vertex colouring
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).45 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!