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,[1][2] making graphs with few cliques of interest in computational graph theory, network analysis, and other branches of applied mathematics.[3] Informally, a family of graphs has few cliques if the graphs do not have a large number of large clusters.
- The Turán graph has an exponential number of maximal cliques. In particular, this graph has exactly maximal cliques when , which is asymptotically greater than any polynomial function.[4]: 441 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 vertices.[5] So the class of Turán graphs does not have few cliques.
- A tree on vertices has as many maximal cliques as edges, since it contains no triangles by definition. Any tree has exactly edges,[6]: 578 and therefore that number of maximal cliques. So the class of trees has few cliques.
- A chordal graph on vertices has at most maximal cliques,[7]: 49 so chordal graphs have few cliques.
- Any planar graph on vertices has at most maximal cliques,[8] so the class of planar graphs has few cliques.
- Any -vertex graph with boxicity has maximal cliques,[9]: 46 so the class of graphs with bounded boxicity has few cliques.
- Any -vertex graph with degeneracy has at most maximal cliques whenever and ,[10] so the class of graphs with bounded degeneracy has few cliques.
- Let be an intersection graph of convex polytopes in -dimensional Euclidean space whose facets are parallel to hyperplanes. Then the number of maximal cliques of is ,[11]: 274 which is polynomial in for fixed and . Therefore, the class of intersection graphs of convex polytopes in fixed-dimensional Euclidean space with a bounded number of facets has few cliques.
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
Fox, J., Roughgarden, T., Seshadhri, C., Wei, F., & Wein, N. (2020). Finding Cliques in Social Networks: A New Distribution-Free Model. SIAM Journal on Computing, 49(2), 448–464. https://doi.org/10.1137/18M1210459
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