Hardness of computing clique number and chromatic number for Cayley graphs

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

zbMATH Keywords

Goppa codesquotient graphs

Mathematics Subject Classification ID

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