Alex's Notes

❯

❯

Clique (graph)

Nov 03, 20231 min read

maths
graph-theory

Clique (graph)

In an undirected graph a set of vertices is a clique if the induced subgraph on is the complete graph on . (i.e. .)

Graph View

Backlinks

Week 10 - Graph problem complexity
Clique of a given size problem is NP-complete
Clique of a given size problem is in NP
Clique of a given size problem
Cliques in G are independent sets in the complement
Independent set of a given size is NP-complete
Max clique problem (graph)
Max clique problem is NP-hard
The k-colourings problem is NP-complete

Created with Quartz v4.5.1 © 2025

GitHub
Discord Community