38:
304:
is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique. Some authors define cliques in a way that requires them to be maximal, and use other terminology for complete subgraphs that are not
800:
is a notion of the complexity of a graph in terms of the minimum number of distinct vertex labels needed to build up the graph from disjoint unions, relabeling operations, and operations that connect all pairs of vertices with given labels. The graphs with clique-width one are exactly the disjoint
512:
933:
in an article using less technical terms. Both works deal with uncovering cliques in a social network using matrices. For continued efforts to model social cliques graph-theoretically, see e.g.
459:
182:. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in
1833:
Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection",
454:
176:
152:
960:
data as one of finding the minimum number of changes needed to transform a graph describing the data into a graph formed as the disjoint union of cliques;
988:
as one of finding maximum cliques in a graph that has as its vertices characteristics of the species, where two vertices share an edge if there exists a
58:
The 11 light blue triangles form maximal cliques. The two dark blue 4-cliques are both maximum and maximal, and the clique number of the graph is 4.
1903:
665:
is a graph whose edges can be covered by edge-disjoint cliques in such a way that each vertex belongs to exactly two of the cliques in the cover.
1223:
Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications",
1000:
as a problem of finding cliques in a graph whose vertices represent positions of subunits of the protein. And by searching for cliques in a
229:
of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in
568:
381:
of a graph is a subset of vertices with the property that each maximum clique of the graph contains at least one vertex in the subset.
1647:
1326:
Cong, J.; Smith, M. (1993), "A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design",
1752:
Paull, M. C.; Unger, S. H. (1959), "Minimizing the number of states in incompletely specified sequential switching functions",
1008:
found clusters of proteins that interact closely with each other and have few interactions with proteins outside the cluster.
1562:
1511:
1308:
1954:
Tanay, Amos; Sharan, Roded; Shamir, Ron (2002), "Discovering statistically significant biclusters in gene expression data",
1027:
use them to design efficient circuits for computing partially specified
Boolean functions. Cliques have also been used in
1540:
1444:
1353:
1035:
describe an application of cliques in finding a hierarchical partition of an electronic circuit into smaller subunits.
805:
599:
549:
343:
1028:
1012:
is a method for simplifying complex biological networks by finding cliques and related structures in these networks.
874:
579:
507:{\displaystyle \scriptstyle \left\lfloor {\frac {n}{2}}\right\rfloor \cdot \left\lceil {\frac {n}{2}}\right\rceil }
1031:: a large clique in an incompatibility graph of possible faults provides a lower bound on the size of a test set.
1862:
Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure",
1400:
Doreian, Patrick; Woodard, Katherine L. (1994), "Defining and locating cores and boundaries of social networks",
1371:
Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility",
1001:
1589:
Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), "A combinatorial algorithm for calculating ligand binding",
1205:
386:
17:
575:
2056:
1721:
1901:
Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks",
997:
187:
436:. If a graph has sufficiently many edges, it must contain a large clique. For instance, every graph with
894:
711:
621:
620:
is a graph whose vertices can be ordered into a perfect elimination ordering, an ordering such that the
824:
882:
535:
vertices can have at most 3 maximal cliques. The graphs meeting this bound are the MoonâMoser graphs
1876:
1266:
1091:
878:
844:
639:
is a graph all of whose induced subgraphs have the property that any maximal clique intersects any
406:
281:, such that every two distinct vertices are adjacent. This is equivalent to the condition that the
1336:
869:
is the computational problem of finding a maximum clique, or all cliques, in a given graph. It is
1521:
Hamzaoglu, I.; Patel, J. H. (1998), "Test set compaction algorithms for combinational circuits",
832:
640:
131:
31:
1871:
1804:
1561:(1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.),
1331:
1261:
1016:
1968:
610:
268:
425:
398:
problem concerns finding as few cliques as possible that include every vertex in the graph.
1944:
Sugihara, George (1984), "Graph theory, homology and food webs", in Levin, Simon A. (ed.),
1744:
1618:
1318:
1252:
Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar (1999), "Clustering gene expression patterns.",
1009:
698:
Additionally, many other mathematical constructions involve cliques in graphs. Among them,
198:, but despite this hardness result, many algorithms for finding cliques have been studied.
413:
of a graph is the minimum number of bicliques needed to cover all the edges of the graph.
8:
836:
691:
517:
410:
1821:
1790:
1703:
1622:
1606:
1546:
1479:
1388:
1359:
1240:
816:
739:
and an edge connecting two cliques that differ by a single vertex. It is an example of
439:
161:
137:
1927:
590:
Several important classes of graphs may be defined or characterized by their cliques:
2029:
2010:
1973:
1932:
1889:
1850:
1695:
1610:
1536:
1507:
1483:
1413:
1349:
1304:
1279:
1047:
989:
985:
1825:
1707:
1550:
1291:
Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), "Maximum clique transversals",
650:
is a graph whose maximal cliques can be ordered in such a way that, for each vertex
1963:
1922:
1912:
1881:
1842:
1813:
1782:
1761:
1730:
1685:
1677:
1637:
1598:
1526:
1500:
1471:
1409:
1380:
1341:
1296:
1295:, Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlin, pp. 32â43,
1271:
1244:
1232:
1197:
1054:
use cliques to model the positions in which two chemicals will bind to each other.
973:
890:
862:
677:
673:
561:
521:
391:
282:
250:
183:
155:
127:
103:
77:
2033:
1571:
1363:
1201:
1094:
subgraphs was originally phrased in topological rather than graph-theoretic terms.
808:
of a graph is the minimum number of cliques needed to cover all the graph's edges.
1740:
1558:
1425:
1314:
957:
906:
557:
1985:
1817:
1665:
1475:
949:
926:
866:
856:
744:
703:
647:
294:
230:
222:
202:
191:
179:
1690:
968:
problem for expression data in which the clusters are required to be cliques.
543:
316:, is a clique, such that there is no clique with more vertices. Moreover, the
2050:
1765:
1668:; Perry, Albert D. (1949), "A method of matrix analysis of group structure",
1491:
902:
728:
687:
is a graph in which some clique contains at least one endpoint of every edge.
669:
617:
595:
206:
2014:
1917:
1802:
Prihar, Z. (1956), "Topological properties of telecommunications networks",
1642:
1421:
1300:
1275:
1977:
1936:
1885:
1854:
1699:
1495:
1462:
Festinger, Leon (1949), "The analysis of sociograms using matrix algebra",
1429:
1283:
1087:
965:
898:
840:
812:
797:
794:
is a method for combining two graphs by merging them along a shared clique.
740:
395:
67:
1893:
1602:
1531:
1345:
390:, in the sense that every clique corresponds to an independent set in the
297:. In some cases, the term clique may also refer to the subgraph directly.
1063:
870:
828:
684:
606:
553:
433:
429:
195:
63:
917:
The word "clique", in its graph-theoretic usage, arose from the work of
1794:
1735:
1681:
1392:
1236:
977:
791:
662:
1846:
2038:
2019:
1716:
1523:
Proc. 1998 IEEE/ACM International
Conference on Computer-Aided Design
1039:
886:
186:: the task of finding whether there is a clique of a given size in a
1786:
1384:
1182:
775:
is the clique whose vertices belong to at least two of the cliques
583:
351:
is the smallest number of cliques that together cover all edges of
1121:
694:
is a graph that has no cliques other than its vertices and edges.
636:
524:
contains a clique with at least a logarithmic number of vertices.
1293:
Graph-theoretic concepts in computer science (Boltenhagen, 2001)
1050:
that have a high degree of similarity with a target structure.
922:
421:
Mathematical results concerning cliques include the following.
226:
89:
889:
for computing cliques have been developed, either running in
37:
205:
goes back at least to the graph-theoretic reformulation of
1773:
Peay, Edmund R. (1974), "Hierarchical clique structures",
1222:
1139:
51:
19 Ă 3-vertex cliques (light and dark blue triangles), and
1832:
1043:
552:, still unproven, relates the size of the largest clique
115:
1948:, Proc. Symp. Appl. Math., vol. 30, pp. 83â101
1097:
130:
such that every two distinct vertices in the clique are
1490:
1127:
2027:
1183:"A graph-theoretic definition of a sociometric clique"
463:
1835:
Journal of
Chemical Information and Computer Sciences
1328:
1023:
uses cliques to analyze communications networks, and
462:
442:
164:
140:
118:
109:
92:
83:
1251:
953:
112:
86:
1570:, New York: Plenum, pp. 85â103, archived from
823:Closely related concepts to complete subgraphs are
106:
80:
1988:(1941), "On an extremal problem in graph theory",
1623:"Sur le problĂšme des courbes gauches en Topologie"
1588:
1499:
1051:
506:
448:
170:
146:
1953:
961:
672:is a graph in which the clique number equals the
546:arising as the extremal cases in TurĂĄn's theorem.
334:is the number of vertices in a maximum clique in
2048:
1109:
2008:
1904:Proceedings of the National Academy of Sciences
1145:
952:have been modeled using cliques. For instance,
1861:
1520:
1399:
1163:
993:
942:
925:(groups of people who all know each other) in
1420:
1290:
1103:
210:
735:) with a vertex for every clique in a graph
1900:
1005:
897:) or specialized to graph families such as
1751:
1617:
1370:
1140:Barthélemy, Leclerc & Monjardet (1986)
1083:
1024:
981:
578:states that families of graphs defined by
1967:
1926:
1916:
1875:
1734:
1714:
1689:
1664:
1641:
1530:
1461:
1335:
1325:
1265:
1032:
930:
918:
528:
514:edges must contain a three-vertex clique.
218:
1943:
1754:IRE Transactions on Electronic Computers
969:
36:
1128:Graham, Rothschild & Spencer (1990)
1046:use cliques to describe chemicals in a
921:, who used complete subgraphs to model
905:for which the problem can be solved in
847:subdivisions and minors, respectively.
370:whose union covers the set of vertices
54:2 Ă 4-vertex cliques (dark blue areas).
14:
2049:
1969:10.1093/bioinformatics/18.suppl_1.S136
1801:
1020:
747:on the cliques of a graph: the median
27:Adjacent subset of an undirected graph
2028:
2009:
1984:
1430:"A combinatorial problem in geometry"
1115:
721:) with a simplex for every clique in
366:is the smallest number of cliques of
45:23 Ă 1-vertex cliques (the vertices),
1772:
1557:
1180:
1151:
954:Ben-Dor, Shamir & Yakhini (1999)
938:
934:
1564:Complexity of Computer Computations
850:
582:have either large cliques or large
24:
1591:Journal of Computational Chemistry
1052:Kuhl, Crippen & Friesen (1983)
984:describe the problem of inferring
929:. The same definition was used by
571:relates graph coloring to cliques.
48:42 Ă 2-vertex cliques (the edges),
25:
2068:
2002:
1506:, New York: John Wiley and Sons,
1190:Journal of Mathematical Sociology
1029:automatic test pattern generation
962:Tanay, Sharan & Shamir (2002)
221:, who used complete subgraphs in
1719:(1965), "On cliques in graphs",
1254:Journal of Computational Biology
992:combining those two characters.
956:model the problem of clustering
827:of complete graphs and complete
658:are consecutive in the ordering.
580:forbidden graph characterization
126:) is a subset of vertices of an
102:
76:
1653:from the original on 2018-07-23
1450:from the original on 2020-05-22
1211:from the original on 2011-05-03
912:
520:states that every graph or its
384:The opposite of a clique is an
134:. That is, a clique of a graph
1157:
1133:
1076:
875:Karp's 21 NP-complete problems
632:in the ordering form a clique.
416:
236:
13:
1:
1722:Israel Journal of Mathematics
1202:10.1080/0022250X.1973.9989826
1173:
1104:Chang, Kloks & Lee (2001)
948:Many different problems from
569:ErdĆsâFaberâLovĂĄsz conjecture
1990:Matematikai Ă©s Fizikai Lapok
1864:Journal of Molecular Biology
1414:10.1016/0378-8733(94)90013-2
1164:Hamzaoglu & Patel (1998)
998:protein structure prediction
994:Samudrala & Moult (1998)
943:Doreian & Woodard (1994)
7:
1057:
1002:proteinâprotein interaction
879:fixed-parameter intractable
743:, and is associated with a
712:abstract simplicial complex
432:on the size of a clique in
407:complete bipartite subgraph
211:ErdĆs & Szekeres (1935)
10:
2073:
1818:10.1109/JRPROC.1956.275149
1476:10.1177/001872674900200205
1090:by forbidden complete and
854:
843:by forbidden complete and
379:maximum clique transversal
29:
1225:Journal of Classification
1181:Alba, Richard D. (1973),
1006:Spirin & Mirny (2003)
731:is an undirected graph Îș(
654:, the cliques containing
527:According to a result of
1766:10.1109/TEC.1959.5222697
1069:
1025:Paull & Unger (1959)
982:Day & Sankoff (1986)
542:, a special case of the
1962:(Suppl. 1): S136âS144,
1918:10.1073/pnas.2032324100
1643:10.4064/fm-15-1-271-283
1630:Fundamenta Mathematicae
1301:10.1007/3-540-45477-2_5
1276:10.1089/106652799318274
1033:Cong & Smith (1993)
919:Luce & Perry (1949)
895:BronâKerbosch algorithm
819:of its maximal cliques.
641:maximal independent set
576:ErdĆsâHajnal conjecture
529:Moon & Moser (1965)
456:vertices and more than
401:A related concept is a
219:Luce & Perry (1949)
32:Clique (disambiguation)
1886:10.1006/jmbi.1998.1689
1805:Proceedings of the IRE
1437:Compositio Mathematica
1017:electrical engineering
972:uses cliques to model
611:biconnected components
508:
450:
201:Although the study of
172:
148:
59:
1619:Kuratowski, Kazimierz
1603:10.1002/jcc.540050105
1532:10.1145/288548.288615
1346:10.1145/157485.165119
885:. Nevertheless, many
628:that come later than
550:Hadwiger's conjecture
509:
451:
173:
149:
40:
2057:Graph theory objects
1525:, pp. 283â289,
1330:, pp. 755â760,
1082:The earlier work by
1044:Rhodes et al. (2003)
1010:Power graph analysis
833:Kuratowski's theorem
600:connected components
460:
440:
162:
138:
30:For other uses, see
1911:(21): 12123â12128,
883:hard to approximate
806:intersection number
763:) of three cliques
692:triangle-free graph
643:in a single vertex.
411:bipartite dimension
360:clique cover number
344:intersection number
267:is a subset of the
2030:Weisstein, Eric W.
2011:Weisstein, Eric W.
1946:Population Biology
1736:10.1007/BF02760024
1691:10.1007/BF02289146
1682:10.1007/BF02289146
1494:; Rothschild, B.;
1373:Systematic Zoology
1237:10.1007/BF01894188
1092:complete bipartite
986:evolutionary trees
964:discuss a similar
845:complete bipartite
817:intersection graph
815:of a graph is the
801:unions of cliques.
504:
503:
446:
203:complete subgraphs
168:
144:
60:
1847:10.1021/ci025605o
1513:978-0-471-50046-9
1310:978-3-540-42707-0
1084:Kuratowski (1930)
1048:chemical database
990:perfect phylogeny
974:ecological niches
831:. In particular,
609:is a graph whose
598:is a graph whose
497:
476:
449:{\displaystyle n}
171:{\displaystyle G}
147:{\displaystyle G}
16:(Redirected from
2064:
2043:
2042:
2024:
2023:
1997:
1992:(in Hungarian),
1980:
1971:
1949:
1939:
1930:
1920:
1896:
1879:
1857:
1828:
1797:
1768:
1747:
1738:
1710:
1693:
1660:
1659:
1658:
1652:
1645:
1627:
1613:
1584:
1583:
1582:
1576:
1569:
1559:Karp, Richard M.
1553:
1534:
1516:
1505:
1486:
1457:
1456:
1455:
1449:
1434:
1426:Szekeres, George
1416:
1395:
1366:
1339:
1321:
1286:
1269:
1260:(3â4): 281â297,
1247:
1218:
1217:
1216:
1210:
1187:
1167:
1161:
1155:
1149:
1143:
1137:
1131:
1125:
1119:
1113:
1107:
1101:
1095:
1080:
931:Festinger (1949)
891:exponential time
863:computer science
851:Computer science
837:Wagner's theorem
678:induced subgraph
674:chromatic number
562:chromatic number
556:in a graph (its
531:, a graph with 3
522:complement graph
518:Ramsey's theorem
513:
511:
510:
505:
502:
498:
490:
481:
477:
469:
455:
453:
452:
447:
392:complement graph
373:
369:
365:
354:
350:
337:
333:
329:
315:
292:
288:
283:induced subgraph
280:
266:
251:undirected graph
248:
184:computer science
177:
175:
174:
169:
156:induced subgraph
153:
151:
150:
145:
128:undirected graph
125:
124:
121:
120:
117:
114:
111:
108:
99:
98:
95:
94:
91:
88:
85:
82:
21:
2072:
2071:
2067:
2066:
2065:
2063:
2062:
2061:
2047:
2046:
2034:"Clique Number"
2005:
2000:
1787:10.2307/2786466
1666:Luce, R. Duncan
1656:
1654:
1650:
1625:
1580:
1578:
1574:
1567:
1543:
1514:
1464:Human Relations
1453:
1451:
1447:
1432:
1402:Social Networks
1385:10.2307/2413432
1356:
1311:
1214:
1212:
1208:
1185:
1176:
1171:
1170:
1162:
1158:
1150:
1146:
1138:
1134:
1126:
1122:
1114:
1110:
1102:
1098:
1086:characterizing
1081:
1077:
1072:
1060:
970:Sugihara (1984)
958:gene expression
927:social networks
915:
907:polynomial time
859:
853:
624:of each vertex
558:Hadwiger number
541:
489:
485:
468:
464:
461:
458:
457:
441:
438:
437:
426:TurĂĄn's theorem
419:
387:independent set
371:
367:
363:
352:
348:
335:
331:
320:
313:
290:
286:
272:
253:
246:
239:
223:social networks
163:
160:
159:
139:
136:
135:
105:
101:
79:
75:
57:
35:
28:
23:
22:
15:
12:
11:
5:
2070:
2060:
2059:
2045:
2044:
2025:
2004:
2003:External links
2001:
1999:
1998:
1982:
1956:Bioinformatics
1951:
1941:
1898:
1877:10.1.1.64.8918
1870:(1): 287â302,
1859:
1841:(2): 443â448,
1830:
1812:(7): 927â933,
1799:
1770:
1760:(3): 356â367,
1749:
1712:
1662:
1615:
1586:
1555:
1542:978-1581130089
1541:
1518:
1512:
1496:Spencer, J. H.
1488:
1470:(2): 153â158,
1459:
1418:
1408:(4): 267â293,
1397:
1379:(2): 224â229,
1368:
1355:978-0897915779
1354:
1323:
1309:
1288:
1267:10.1.1.34.5341
1249:
1231:(2): 187â224,
1220:
1196:(1): 113â126,
1177:
1175:
1172:
1169:
1168:
1156:
1144:
1132:
1120:
1108:
1096:
1074:
1073:
1071:
1068:
1067:
1066:
1059:
1056:
950:bioinformatics
914:
911:
903:perfect graphs
867:clique problem
857:Clique problem
855:Main article:
852:
849:
821:
820:
809:
802:
795:
788:
745:median algebra
725:
704:clique complex
696:
695:
688:
681:
666:
659:
648:interval graph
644:
633:
614:
603:
588:
587:
572:
565:
547:
539:
525:
515:
501:
496:
493:
488:
484:
480:
475:
472:
467:
445:
418:
415:
374:of the graph.
310:maximum clique
302:maximal clique
295:complete graph
238:
235:
231:bioinformatics
192:clique problem
167:
143:
56:
55:
52:
49:
46:
42:
26:
18:Maximum clique
9:
6:
4:
3:
2:
2069:
2058:
2055:
2054:
2052:
2041:
2040:
2035:
2031:
2026:
2022:
2021:
2016:
2012:
2007:
2006:
1995:
1991:
1987:
1983:
1979:
1975:
1970:
1965:
1961:
1957:
1952:
1947:
1942:
1938:
1934:
1929:
1924:
1919:
1914:
1910:
1906:
1905:
1899:
1895:
1891:
1887:
1883:
1878:
1873:
1869:
1865:
1860:
1856:
1852:
1848:
1844:
1840:
1836:
1831:
1827:
1823:
1819:
1815:
1811:
1807:
1806:
1800:
1796:
1792:
1788:
1784:
1780:
1776:
1771:
1767:
1763:
1759:
1755:
1750:
1746:
1742:
1737:
1732:
1728:
1724:
1723:
1718:
1715:Moon, J. W.;
1713:
1709:
1705:
1701:
1697:
1692:
1687:
1683:
1679:
1676:(2): 95â116,
1675:
1671:
1670:Psychometrika
1667:
1663:
1649:
1644:
1639:
1635:
1632:(in French),
1631:
1624:
1620:
1616:
1612:
1608:
1604:
1600:
1596:
1592:
1587:
1577:on 2011-06-29
1573:
1566:
1565:
1560:
1556:
1552:
1548:
1544:
1538:
1533:
1528:
1524:
1519:
1515:
1509:
1504:
1503:
1502:Ramsey Theory
1497:
1493:
1489:
1485:
1481:
1477:
1473:
1469:
1465:
1460:
1446:
1442:
1438:
1431:
1427:
1423:
1419:
1415:
1411:
1407:
1403:
1398:
1394:
1390:
1386:
1382:
1378:
1374:
1369:
1365:
1361:
1357:
1351:
1347:
1343:
1338:
1337:10.1.1.32.735
1333:
1329:
1324:
1320:
1316:
1312:
1306:
1302:
1298:
1294:
1289:
1285:
1281:
1277:
1273:
1268:
1263:
1259:
1255:
1250:
1246:
1242:
1238:
1234:
1230:
1226:
1221:
1207:
1203:
1199:
1195:
1191:
1184:
1179:
1178:
1165:
1160:
1153:
1148:
1141:
1136:
1129:
1124:
1117:
1112:
1105:
1100:
1093:
1089:
1088:planar graphs
1085:
1079:
1075:
1065:
1062:
1061:
1055:
1053:
1049:
1045:
1041:
1036:
1034:
1030:
1026:
1022:
1021:Prihar (1956)
1018:
1013:
1011:
1007:
1003:
999:
995:
991:
987:
983:
979:
975:
971:
967:
963:
959:
955:
951:
946:
944:
940:
936:
932:
928:
924:
920:
910:
908:
904:
900:
899:planar graphs
896:
893:(such as the
892:
888:
884:
880:
877:. It is also
876:
872:
868:
864:
858:
848:
846:
842:
841:planar graphs
839:characterize
838:
834:
830:
826:
818:
814:
810:
807:
803:
799:
796:
793:
789:
786:
782:
778:
774:
770:
766:
762:
758:
754:
750:
746:
742:
738:
734:
730:
729:simplex graph
726:
724:
720:
716:
713:
709:
705:
701:
700:
699:
693:
689:
686:
682:
679:
675:
671:
670:perfect graph
667:
664:
660:
657:
653:
649:
645:
642:
638:
634:
631:
627:
623:
619:
618:chordal graph
615:
612:
608:
604:
601:
597:
596:cluster graph
593:
592:
591:
585:
581:
577:
573:
570:
566:
563:
559:
555:
551:
548:
545:
538:
534:
530:
526:
523:
519:
516:
499:
494:
491:
486:
482:
478:
473:
470:
465:
443:
435:
431:
427:
424:
423:
422:
414:
412:
408:
404:
399:
397:
393:
389:
388:
382:
380:
375:
361:
356:
346:
345:
339:
327:
323:
319:
318:clique number
311:
306:
303:
298:
296:
284:
279:
275:
270:
264:
260:
256:
252:
244:
234:
232:
228:
224:
220:
216:
212:
208:
207:Ramsey theory
204:
199:
197:
193:
189:
185:
181:
165:
157:
141:
133:
129:
123:
97:
73:
69:
65:
53:
50:
47:
44:
43:
41:A graph with
39:
33:
19:
2037:
2018:
1993:
1989:
1959:
1955:
1945:
1908:
1902:
1867:
1863:
1838:
1834:
1809:
1803:
1781:(1): 54â65,
1778:
1774:
1757:
1753:
1726:
1720:
1673:
1669:
1655:, retrieved
1633:
1629:
1597:(1): 24â34,
1594:
1590:
1579:, retrieved
1572:the original
1563:
1522:
1501:
1467:
1463:
1452:, retrieved
1440:
1436:
1405:
1401:
1376:
1372:
1327:
1292:
1257:
1253:
1228:
1224:
1213:, retrieved
1193:
1189:
1159:
1147:
1135:
1123:
1116:TurĂĄn (1941)
1111:
1099:
1078:
1037:
1014:
966:biclustering
947:
916:
913:Applications
860:
829:graph minors
825:subdivisions
822:
813:clique graph
798:Clique-width
784:
780:
776:
772:
768:
764:
760:
756:
752:
748:
741:median graph
736:
732:
722:
718:
714:
707:
697:
655:
651:
629:
625:
613:are cliques.
602:are cliques.
589:
544:TurĂĄn graphs
536:
532:
434:dense graphs
420:
402:
400:
396:clique cover
385:
383:
378:
376:
359:
357:
342:
340:
325:
321:
317:
312:of a graph,
309:
307:
301:
299:
277:
273:
262:
258:
254:
242:
240:
214:
200:
71:
68:graph theory
64:mathematical
61:
1986:TurĂĄn, Paul
1636:: 271â283,
1443:: 463â470,
1422:ErdĆs, Paul
1152:Karp (1972)
1142:, page 200.
1064:Clique game
939:Peay (1974)
935:Alba (1973)
871:NP-complete
706:of a graph
685:split graph
607:block graph
430:lower bound
417:Mathematics
362:of a graph
330:of a graph
289:induced by
237:Definitions
217:comes from
213:, the term
196:NP-complete
1775:Sociometry
1657:2009-12-19
1581:2009-12-13
1492:Graham, R.
1454:2009-12-19
1215:2009-12-14
1174:References
887:algorithms
792:clique-sum
663:line graph
2039:MathWorld
2020:MathWorld
1996:: 436â452
1872:CiteSeerX
1729:: 23â28,
1717:Moser, L.
1611:122923018
1484:143609308
1332:CiteSeerX
1262:CiteSeerX
1040:chemistry
1004:network,
978:food webs
873:, one of
676:in every
622:neighbors
584:cocliques
560:) to its
483:⋅
305:maximal.
225:to model
2051:Category
2015:"Clique"
1978:12169541
1937:14517352
1855:12653507
1826:51654879
1708:16186758
1700:18152948
1648:archived
1621:(1930),
1551:12258606
1498:(1990),
1445:archived
1428:(1935),
1284:10582567
1206:archived
1058:See also
500:⌉
487:⌈
479:⌋
466:⌊
428:gives a
403:biclique
269:vertices
249:, in an
180:complete
178:that is
132:adjacent
66:area of
1894:9636717
1795:2786466
1745:0182577
1393:2413432
1319:1905299
1245:6092438
923:cliques
637:cograph
540:3,3,...
227:cliques
62:In the
1976:
1935:
1928:218723
1925:
1892:
1874:
1853:
1824:
1793:
1743:
1706:
1698:
1609:
1549:
1539:
1510:
1482:
1391:
1364:525253
1362:
1352:
1334:
1317:
1307:
1282:
1264:
1243:
996:model
941:, and
881:, and
865:, the
783:, and
771:, and
710:is an
409:. The
394:. The
243:clique
215:clique
154:is an
72:clique
1822:S2CID
1791:JSTOR
1704:S2CID
1651:(PDF)
1626:(PDF)
1607:S2CID
1575:(PDF)
1568:(PDF)
1547:S2CID
1480:S2CID
1448:(PDF)
1433:(PDF)
1389:JSTOR
1360:S2CID
1241:S2CID
1209:(PDF)
1186:(PDF)
1070:Notes
554:minor
293:is a
194:) is
190:(the
188:graph
1974:PMID
1933:PMID
1890:PMID
1851:PMID
1758:EC-8
1696:PMID
1537:ISBN
1508:ISBN
1350:ISBN
1305:ISBN
1280:PMID
835:and
811:The
804:The
790:The
702:The
574:The
567:The
405:, a
358:The
341:The
70:, a
1964:doi
1923:PMC
1913:doi
1909:100
1882:doi
1868:279
1843:doi
1814:doi
1783:doi
1762:doi
1731:doi
1686:hdl
1678:doi
1638:doi
1599:doi
1527:doi
1472:doi
1410:doi
1381:doi
1342:doi
1297:doi
1272:doi
1233:doi
1198:doi
1038:In
1015:In
976:in
901:or
861:In
646:An
347:of
285:of
257:= (
209:by
158:of
100:or
2053::
2036:,
2032:,
2017:,
2013:,
1994:48
1972:,
1960:18
1958:,
1931:,
1921:,
1907:,
1888:,
1880:,
1866:,
1849:,
1839:43
1837:,
1820:,
1810:44
1808:,
1789:,
1779:37
1777:,
1756:,
1741:MR
1739:,
1725:,
1702:,
1694:,
1684:,
1674:14
1672:,
1646:,
1634:15
1628:,
1605:,
1593:,
1545:,
1535:,
1478:,
1466:,
1439:,
1435:,
1424:;
1406:16
1404:,
1387:,
1377:35
1375:,
1358:,
1348:,
1340:,
1315:MR
1313:,
1303:,
1278:,
1270:,
1256:,
1239:,
1227:,
1204:,
1192:,
1188:,
1042:,
1019:,
980:.
945:.
937:,
909:.
779:,
767:,
727:A
690:A
683:A
668:A
661:A
635:A
616:A
605:A
594:A
377:A
355:.
338:.
308:A
300:A
276:â
271:,
261:,
245:,
241:A
233:.
90:iË
1981:.
1966::
1950:.
1940:.
1915::
1897:.
1884::
1858:.
1845::
1829:.
1816::
1798:.
1785::
1769:.
1764::
1748:.
1733::
1727:3
1711:.
1688::
1680::
1661:.
1640::
1614:.
1601::
1595:5
1585:.
1554:.
1529::
1517:.
1487:.
1474::
1468:2
1458:.
1441:2
1417:.
1412::
1396:.
1383::
1367:.
1344::
1322:.
1299::
1287:.
1274::
1258:6
1248:.
1235::
1229:3
1219:.
1200::
1194:3
1166:.
1154:.
1130:.
1118:.
1106:.
787:.
785:C
781:B
777:A
773:C
769:B
765:A
761:C
759:,
757:B
755:,
753:A
751:(
749:m
737:G
733:G
723:G
719:G
717:(
715:X
708:G
680:.
656:v
652:v
630:v
626:v
586:.
564:.
537:K
533:n
495:2
492:n
474:2
471:n
444:n
372:V
368:G
364:G
353:G
349:G
336:G
332:G
328:)
326:G
324:(
322:Ï
314:G
291:C
287:G
278:V
274:C
265:)
263:E
259:V
255:G
247:C
166:G
142:G
122:/
119:k
116:ÉȘ
113:l
110:k
107:Ë
104:/
96:/
93:k
87:l
84:k
81:Ë
78:/
74:(
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
