Cliques in Odd-Minor-Free Graphs

Kawarabayashi, K. and Wood, D. R.

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.

Cite as: Kawarabayashi, K. and Wood, D. R. (2012). Cliques in Odd-Minor-Free Graphs. In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 133-138

(from crpit.com) (local if available)