Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Graphs with few cliques
open-in-new
<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a <a href="/facts/Class_(mathematics)/F5EmDd9b">class</a> of <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graphs</a> is said to have few cliques if every member of the class has a <a href="/facts/Time_complexity/77T62gmf">polynomial number</a> of <a href="/facts/Maximal_clique/XK9ppLz5">maximal cliques.</a> Certain generally <a href="/facts/NP-hardness/mQeNPv4R">NP-hard</a> computational problems are solvable in polynomial time on such classes of graphs, making graphs with few cliques of interest in computational <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, <a href="/facts/Social_network_analysis/CsJIFjVw">network analysis</a>, and other branches of <a href="/facts/Applied_mathematics/qyqklXXm">applied mathematics</a>. Informally, a family of graphs has few cliques if the graphs do not have a large number of large <a href="/facts/Cluster_(statistics)/HUeDnWPt">clusters.</a> </p>