Graphs with few cliques

In graph theory, a class of graphs is said to have few cliques if every member of the class has a polynomial number of maximal cliques.^[1] Certain generally NP-hard computational problems are solvable in polynomial time on such classes of graphs^[2], making graphs with few cliques of interest in computational graph theory, network analysis, and other branches of applied mathematics.

Definition

Let $X$ be a class of graphs. If for every $n$ -vertex graph $G$ in $X$ , there exists a polynomial $f(n)$ such that $G$ has $O(f(n))$ maximal cliques, then $X$ is said to be a class of graphs with few cliques.^[1]

Examples

The Turán graph $T(n,\lceil n/3\rceil )$ has an exponential number of maximal cliques. In particular, this graph has exactly $3^{n/3}$ maximal cliques when $n\equiv 0\mod 3$ , which is asymptotically greater than any polynomial function. This graph is sometimes called the Moon-Moser graph, after Moon & Moser showed in 1965 that this graph has the largest number of maximal cliques among all graphs on $n$ vertices.^[3] So the class of Turán graphs does not have few cliques.
A tree $T$ on $n$ vertices has as many maximal cliques as edges, since it contains no triangles by definition. Any tree has exactly $n-1$ edges^[4]^: 578, and therefore that number of maximal cliques. So the class of trees has few cliques.
A chordal graph on $n$ vertices has at most $n$ maximal cliques^[5]^: 49, so chordal graphs have few cliques.
Any planar graph on $n$ vertices has at most $8n-16$ maximal cliques^[6], so the class of planar graphs has few cliques.
Any $n$ -vertex graph with boxicity $b$ has $O(n^{b})$ maximal cliques^[7]^: 46, so the class of graphs with bounded boxicity has few cliques.
Any $n$ -vertex graph with degeneracy $d$ has at most ${\textstyle (n-d)3^{d/3}}$ maximal cliques whenever $d\equiv 0\mod 3$ and $n\geq d+3$ ^[8], so the class of graphs with bounded degeneracy has few cliques.
Let $G$ be an intersection graph of $n$ convex polytopes in $d$ -dimensional Euclidean space whose facets are parallel to $k$ hyperplanes. Then the number of maximal cliques of $G$ is ${\textstyle O\left(n^{dk^{d+1}}\right)}$ ^[9]^: 274, which is polynomial in $n$ for fixed $d$ and $k$ . Therefore the class of intersection graphs of convex polytopes in fixed-dimensional Euclidean space with a bounded number of facets has few cliques.

References

^ ^a ^b Prisner, E. (1995). Graphs with Few Cliques. In Y. Alavi & A. Schwenk (Eds.), Graph theory, combinatorics, and algorithms: proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs (pp. 945–956). New York, N. Y: Wiley.
^ Rosgen, B., & Stewart, L. (2007). Complexity results on graphs with few cliques. Discrete Mathematics & Theoretical Computer Science, Vol. 9 no. 1 (Graph and Algorithms), 387. https://doi.org/10.46298/dmtcs.387
^ Moon, J. W., & Moser, L. (1965). On cliques in graphs. Israel Journal of Mathematics, 3(1), 23–28. https://doi.org/10.1007/BF02760024
^ Pahl, P. J., & Damrath, R. (2001). Mathematical foundations of computational engineering: a handbook. Berlin ; New York: Springer.
^ Gavril, F. (1974). The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1), 47–56. https://doi.org/10.1016/0095-8956(74)90094-X
^ Wood, D. R. (2007). On the Maximum Number of Cliques in a Graph. Graphs and Combinatorics, 23(3), 337–352. https://doi.org/10.1007/s00373-007-0738-8
^ Spinrad, J. P. (2003). Intersection and containment representations. In Efficient graph representations (pp. 31–53). Providence, R.I: American Mathematical Society.
^ Eppstein, D., Löffler, M., & Strash, D. (2010). Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. In O. Cheong, K.-Y. Chwa, & K. Park (Eds.), Algorithms and Computation (Vol. 6506, pp. 403–414). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36
^ Brimkov, V. E., Junosza-Szaniawski, K., Kafer, S., Kratochvíl, J., Pergel, M., Rzążewski, P., et al. (2018). Homothetic polygons and beyond: Maximal cliques in intersection graphs. Discrete Applied Mathematics, 247, 263–277. https://doi.org/10.1016/j.dam.2018.03.046

[:0-1] Prisner, E. (1995). Graphs with Few Cliques. In Y. Alavi & A. Schwenk (Eds.), Graph theory, combinatorics, and algorithms: proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs (pp. 945–956). New York, N. Y: Wiley.

[2] Rosgen, B., & Stewart, L. (2007). Complexity results on graphs with few cliques. Discrete Mathematics & Theoretical Computer Science, Vol. 9 no. 1 (Graph and Algorithms), 387. https://doi.org/10.46298/dmtcs.387

[3] Moon, J. W., & Moser, L. (1965). On cliques in graphs. Israel Journal of Mathematics, 3(1), 23–28. https://doi.org/10.1007/BF02760024

[4] Pahl, P. J., & Damrath, R. (2001). Mathematical foundations of computational engineering: a handbook. Berlin ; New York: Springer.

[5] Gavril, F. (1974). The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1), 47–56. https://doi.org/10.1016/0095-8956(74)90094-X

[6] Wood, D. R. (2007). On the Maximum Number of Cliques in a Graph. Graphs and Combinatorics, 23(3), 337–352. https://doi.org/10.1007/s00373-007-0738-8

[7] Spinrad, J. P. (2003). Intersection and containment representations. In Efficient graph representations (pp. 31–53). Providence, R.I: American Mathematical Society.

[8] Eppstein, D., Löffler, M., & Strash, D. (2010). Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. In O. Cheong, K.-Y. Chwa, & K. Park (Eds.), Algorithms and Computation (Vol. 6506, pp. 403–414). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36

[9] Brimkov, V. E., Junosza-Szaniawski, K., Kafer, S., Kratochvíl, J., Pergel, M., Rzążewski, P., et al. (2018). Homothetic polygons and beyond: Maximal cliques in intersection graphs. Discrete Applied Mathematics, 247, 263–277. https://doi.org/10.1016/j.dam.2018.03.046

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]