2011/08/15 by Ken-ichi Kawarabayashi, Ken‐ichi Kawarabayashi, David R. Wood +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1108.2949
openalex publication_date 2011/08/15 · arxiv created 2012/02/08 · arxiv updated 2012/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper is about: (1) bounds on the number of cliques in a graph in a particular class, and (2) algorithms for listing all cliques in a graph. We present a simple algorithm that lists all cliques in an n-vertex graph in O(n) time per clique. For O(1)-degenerate graphs, such as graphs excluding a fixed minor, we describe a O(n) time algorithm for listing all cliques. We prove that graphs excluding a fixed odd-minor have O(n2) cliques (which is tight), and conclude a O(n3) time algorithm for listing all cliques.