Hardness of computing clique number and chromatic number for Cayley graphs
From MaRDI portal
Publication:518185
DOI10.1016/j.ejc.2016.12.005zbMath1358.05137arXiv1502.00965OpenAlexW2962874215MaRDI QIDQ518185
Brendan Rooney, Chris D. Godsil
Publication date: 28 March 2017
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.00965
Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
On maximal cliques of Cayley graphs over fields ⋮ Strong cliques in vertex‐transitive graphs ⋮ Chromatic numbers of Cayley graphs of abelian groups: a matrix method
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sidon sets in groups and induced subgraphs of Cayley graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Hardness results and spectral techniques for combinatorial problems on circulant graphs
- On the chromatic number of cube-like graphs
- Graphical regular representations of free products of groups
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Homomorphisms of binary Cayley graphs
- Reducibility among Combinatorial Problems
- Intersecting families of permutations