Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949579 | Discrete Applied Mathematics | 2017 | 18 Pages |
Abstract
A circulant graph Cn(a1,â¦,ak) is a graph with n vertices {v0,â¦,vnâ1} such that each vertex vi is adjacent to vertices v(i+aj)modn, for j=1,â¦,k. In this paper we investigate the vertex colouring problem on circulant graphs. We approach the problem in a purely combinatorial way based on an array representation and propose an exact O(k3log2n+n) algorithm for a subclass of 3-chromatic Cn(a1,â¦,ak)'s with kâ¥2, which are characterized in the paper.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
S. Nicoloso, U. Pietropaoli,