Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777430 | European Journal of Combinatorics | 2017 | 20 Pages |
Abstract
Computing the clique number and chromatic number of a general graph are well-known NP-Hard problems. Codenotti et al., (1998) showed that computing clique number and chromatic number are both NP-Hard problems for the class of circulant graphs. We show that computing clique number is NP-Hard for the class of Cayley graphs for the groups Gn, where G is any fixed finite group (e.g., cubelike graphs). We also show that computing chromatic number cannot be done in polynomial time (under the assumption NPâ ZPP) for the same class of graphs. Our presentation uses free Cayley graphs. The proof combines free Cayley graphs with quotient graphs and Goppa codes.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Chris Godsil, Brendan Rooney,