79:
is a clique that is not properly contained in another clique. One can regard a clique as a cluster of vertices, since they are by definition all connected to each other by an edge. The concept of clusters is ubiquitous in
1049:
1308:
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.
348:
842:
422:
874:
807:
1292:
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.),
711:
387:
264:
629:
206:
526:
1109:
1089:
1069:
995:
972:
944:
921:
897:
757:
734:
675:
652:
600:
573:
553:
500:
480:
450:
284:
226:
177:
157:
133:
113:
1111:. Therefore, the class of intersection graphs of convex polytopes in fixed-dimensional Euclidean space with a bounded number of facets has few cliques.
1135:
Graph theory, combinatorics, and algorithms: proceedings of the
Seventh Quadrennial International Conference on the Theory and Applications of Graphs
44:
computational problems are solvable in polynomial time on such classes of graphs, making graphs with few cliques of interest in computational
1167:
Fox, J., Roughgarden, T., Seshadhri, C., Wei, F., & Wein, N. (2020). Finding
Cliques in Social Networks: A New Distribution-Free Model.
432:, after Moon & Moser showed in 1965 that this graph has the largest number of maximal cliques among all graphs on
502:
vertices has as many maximal cliques as edges, since it contains no triangles by definition. Any tree has exactly
1339:
1000:
304:
25:
88:. For that reason, limiting the number of possible maximal cliques has computational ramifications for
812:
737:
392:
56:. Informally, a family of graphs has few cliques if the graphs do not have a large number of large
72:
49:
1237:
Gavril, F. (1974). The intersection graphs of subtrees in trees are exactly the chordal graphs.
847:
762:
680:
1334:
357:
231:
136:
605:
528:
edges, and therefore that number of maximal cliques. So the class of trees has few cliques.
57:
182:
8:
505:
460:
425:
53:
21:
1094:
1074:
1054:
980:
957:
929:
906:
900:
882:
742:
719:
660:
637:
585:
558:
538:
485:
465:
435:
351:
269:
211:
162:
142:
118:
98:
1147:
Rosgen, B., & Stewart, L. (2007). Complexity results on graphs with few cliques.
1132:
Prisner, E. (1995). Graphs with Few
Cliques. In Y. Alavi & A. Schwenk (Eds.),
951:
947:
923:
33:
1297:
1246:
85:
37:
713:
maximal cliques, so the class of graphs with bounded boxicity has few cliques.
299:
1328:
532:
81:
1317:
1266:
579:
45:
17:
1296:(Vol. 6506, pp. 403–414). Berlin, Heidelberg: Springer Berlin Heidelberg.
1279:
1224:
1189:
1134:
41:
1277:
Spinrad, J. P. (2003). Intersection and containment representations. In
974:
1211:
1176:
1156:
89:
655:
1257:
Wood, D. R. (2007). On the
Maximum Number of Cliques in a Graph.
1225:
Mathematical foundations of computational engineering: a handbook
876:, so the class of graphs with bounded degeneracy has few cliques.
428:
than any polynomial function. This graph is sometimes called the
631:
maximal cliques, so the class of planar graphs has few cliques.
1283:(pp. 31–53). Providence, R.I: American Mathematical Society.
1202:
Moon, J. W., & Moser, L. (1965). On cliques in graphs.
354:
of maximal cliques. In particular, this graph has exactly
1187:
Graham, R. L., Knuth, D. E., & Patashnik, O. (1994).
1190:
Concrete mathematics: a foundation for computer science
1149:
1003:
765:
1097:
1077:
1057:
983:
960:
932:
909:
885:
850:
815:
745:
722:
683:
663:
640:
608:
588:
561:
541:
508:
488:
468:
438:
395:
360:
307:
272:
234:
214:
185:
165:
145:
121:
101:
575:
maximal cliques, so chordal graphs have few cliques.
1103:
1083:
1063:
1043:
989:
966:
938:
915:
891:
868:
836:
801:
751:
728:
705:
669:
646:
623:
594:
567:
547:
520:
494:
474:
444:
416:
381:
342:
278:
258:
220:
200:
171:
151:
127:
107:
1326:
1298:https://doi.org/10.1007/978-3-642-17517-6_36
1247:https://doi.org/10.1016/0095-8956(74)90094-X
452:vertices. So the class of Turán graphs does
334:
320:
1318:https://doi.org/10.1016/j.dam.2018.03.046
1267:https://doi.org/10.1007/s00373-007-0738-8
1239:Journal of Combinatorial Theory, Series B
1193:(2nd ed.). Reading, Mass: Addison-Wesley.
830:
829:
410:
409:
977:. Then the number of maximal cliques of
1222:Pahl, P. J., & Damrath, R. (2001).
1044:{\textstyle O\left(n^{dk^{d+1}}\right)}
1327:
343:{\displaystyle T(n,\lceil n/3\rceil )}
1138:(pp. 945–956). New York, N. Y: Wiley.
1128:
1126:
1124:
115:be a class of graphs. If for every
32:if every member of the class has a
13:
1212:https://doi.org/10.1007/BF02760024
1177:https://doi.org/10.1137/18M1210459
1157:https://doi.org/10.46298/dmtcs.387
14:
1351:
1121:
288:class of graphs with few cliques.
1302:
1286:
1280:Efficient graph representations
837:{\displaystyle d\equiv 0\mod 3}
825:
417:{\displaystyle n\equiv 0\mod 3}
405:
1271:
1251:
1231:
1228:. Berlin ; New York: Springer.
1216:
1196:
1181:
1161:
1141:
778:
766:
700:
687:
337:
311:
253:
250:
244:
238:
195:
189:
1:
1204:Israel Journal of Mathematics
1155:(Graph and Algorithms), 387.
1115:
84:, such as on the analysis of
62:
1310:Discrete Applied Mathematics
179:, there exists a polynomial
7:
292:
10:
1356:
1294:Algorithms and Computation
1169:SIAM Journal on Computing
1051:, which is polynomial in
869:{\displaystyle n\geq d+3}
809:maximal cliques whenever
802:{\textstyle (n-d)3^{d/3}}
71:of a graph is a complete
1259:Graphs and Combinatorics
706:{\displaystyle O(n^{b})}
52:, and other branches of
382:{\displaystyle 3^{n/3}}
259:{\displaystyle O(f(n))}
92:on graphs or networks.
1105:
1085:
1065:
1045:
991:
968:
940:
917:
893:
870:
838:
803:
753:
730:
707:
671:
648:
625:
596:
569:
549:
522:
496:
476:
446:
426:asymptotically greater
418:
383:
344:
280:
266:maximal cliques, then
260:
222:
202:
173:
153:
129:
109:
1106:
1086:
1066:
1046:
992:
969:
941:
918:
894:
871:
839:
804:
754:
731:
708:
672:
649:
626:
624:{\displaystyle 8n-16}
602:vertices has at most
597:
570:
555:vertices has at most
550:
523:
497:
477:
447:
419:
389:maximal cliques when
384:
345:
281:
261:
223:
203:
174:
154:
130:
110:
1340:Discrete mathematics
1095:
1075:
1055:
1001:
981:
958:
930:
907:
883:
848:
813:
763:
743:
720:
681:
661:
638:
606:
586:
559:
539:
506:
486:
466:
436:
393:
358:
305:
270:
232:
212:
201:{\displaystyle f(n)}
183:
163:
143:
119:
99:
736:-vertex graph with
654:-vertex graph with
521:{\displaystyle n-1}
54:applied mathematics
1101:
1081:
1061:
1041:
987:
964:
936:
913:
901:intersection graph
889:
866:
834:
799:
749:
726:
703:
667:
644:
621:
592:
565:
545:
518:
492:
472:
442:
414:
379:
352:exponential number
340:
276:
256:
218:
198:
169:
149:
125:
105:
40:Certain generally
1104:{\displaystyle k}
1084:{\displaystyle d}
1064:{\displaystyle n}
990:{\displaystyle G}
967:{\displaystyle k}
939:{\displaystyle d}
916:{\displaystyle n}
892:{\displaystyle G}
752:{\displaystyle d}
729:{\displaystyle n}
670:{\displaystyle b}
647:{\displaystyle n}
595:{\displaystyle n}
568:{\displaystyle n}
548:{\displaystyle n}
495:{\displaystyle n}
475:{\displaystyle T}
456:have few cliques.
445:{\displaystyle n}
279:{\displaystyle X}
221:{\displaystyle G}
172:{\displaystyle X}
152:{\displaystyle G}
128:{\displaystyle n}
108:{\displaystyle X}
34:polynomial number
1347:
1320:
1306:
1300:
1290:
1284:
1275:
1269:
1255:
1249:
1235:
1229:
1220:
1214:
1200:
1194:
1185:
1179:
1165:
1159:
1145:
1139:
1130:
1110:
1108:
1107:
1102:
1090:
1088:
1087:
1082:
1070:
1068:
1067:
1062:
1050:
1048:
1047:
1042:
1040:
1036:
1035:
1034:
1033:
996:
994:
993:
988:
973:
971:
970:
965:
954:are parallel to
945:
943:
942:
937:
924:convex polytopes
922:
920:
919:
914:
898:
896:
895:
890:
875:
873:
872:
867:
843:
841:
840:
835:
808:
806:
805:
800:
798:
797:
793:
758:
756:
755:
750:
735:
733:
732:
727:
712:
710:
709:
704:
699:
698:
676:
674:
673:
668:
653:
651:
650:
645:
630:
628:
627:
622:
601:
599:
598:
593:
574:
572:
571:
566:
554:
552:
551:
546:
527:
525:
524:
519:
501:
499:
498:
493:
481:
479:
478:
473:
451:
449:
448:
443:
430:Moon-Moser graph
423:
421:
420:
415:
388:
386:
385:
380:
378:
377:
373:
349:
347:
346:
341:
330:
286:is said to be a
285:
283:
282:
277:
265:
263:
262:
257:
227:
225:
224:
219:
207:
205:
204:
199:
178:
176:
175:
170:
158:
156:
155:
150:
134:
132:
131:
126:
114:
112:
111:
106:
50:network analysis
38:maximal cliques.
28:is said to have
1355:
1354:
1350:
1349:
1348:
1346:
1345:
1344:
1325:
1324:
1323:
1307:
1303:
1291:
1287:
1276:
1272:
1256:
1252:
1236:
1232:
1221:
1217:
1201:
1197:
1186:
1182:
1166:
1162:
1146:
1142:
1131:
1122:
1118:
1096:
1093:
1092:
1076:
1073:
1072:
1056:
1053:
1052:
1023:
1019:
1015:
1011:
1007:
1002:
999:
998:
982:
979:
978:
959:
956:
955:
948:Euclidean space
931:
928:
927:
908:
905:
904:
884:
881:
880:
849:
846:
845:
814:
811:
810:
789:
785:
781:
764:
761:
760:
744:
741:
740:
721:
718:
717:
694:
690:
682:
679:
678:
662:
659:
658:
639:
636:
635:
607:
604:
603:
587:
584:
583:
560:
557:
556:
540:
537:
536:
507:
504:
503:
487:
484:
483:
467:
464:
463:
437:
434:
433:
394:
391:
390:
369:
365:
361:
359:
356:
355:
326:
306:
303:
302:
295:
271:
268:
267:
233:
230:
229:
213:
210:
209:
184:
181:
180:
164:
161:
160:
144:
141:
140:
120:
117:
116:
100:
97:
96:
86:social networks
65:
12:
11:
5:
1353:
1343:
1342:
1337:
1322:
1321:
1301:
1285:
1270:
1265:(3), 337–352.
1250:
1230:
1215:
1195:
1180:
1175:(2), 448–464.
1160:
1140:
1119:
1117:
1114:
1113:
1112:
1100:
1080:
1060:
1039:
1032:
1029:
1026:
1022:
1018:
1014:
1010:
1006:
986:
963:
935:
912:
888:
877:
865:
862:
859:
856:
853:
833:
828:
824:
821:
818:
796:
792:
788:
784:
780:
777:
774:
771:
768:
748:
725:
714:
702:
697:
693:
689:
686:
666:
643:
632:
620:
617:
614:
611:
591:
576:
564:
544:
529:
517:
514:
511:
491:
471:
457:
441:
413:
408:
404:
401:
398:
376:
372:
368:
364:
339:
336:
333:
329:
325:
322:
319:
316:
313:
310:
294:
291:
275:
255:
252:
249:
246:
243:
240:
237:
217:
197:
194:
191:
188:
168:
148:
124:
104:
95:Formally, let
77:maximal clique
64:
61:
9:
6:
4:
3:
2:
1352:
1341:
1338:
1336:
1333:
1332:
1330:
1319:
1315:
1311:
1305:
1299:
1295:
1289:
1282:
1281:
1274:
1268:
1264:
1260:
1254:
1248:
1244:
1240:
1234:
1227:
1226:
1219:
1213:
1209:
1205:
1199:
1192:
1191:
1184:
1178:
1174:
1170:
1164:
1158:
1154:
1150:
1144:
1137:
1136:
1129:
1127:
1125:
1120:
1098:
1078:
1058:
1037:
1030:
1027:
1024:
1020:
1016:
1012:
1008:
1004:
984:
976:
961:
953:
949:
946:-dimensional
933:
925:
910:
902:
886:
878:
863:
860:
857:
854:
851:
831:
826:
822:
819:
816:
794:
790:
786:
782:
775:
772:
769:
746:
739:
723:
715:
695:
691:
684:
664:
657:
641:
633:
618:
615:
612:
609:
589:
581:
577:
562:
542:
534:
533:chordal graph
530:
515:
512:
509:
489:
469:
462:
458:
455:
439:
431:
427:
411:
406:
402:
399:
396:
374:
370:
366:
362:
353:
331:
327:
323:
317:
314:
308:
301:
297:
296:
290:
289:
273:
247:
241:
235:
215:
192:
186:
166:
146:
138:
122:
102:
93:
91:
87:
83:
82:data analysis
78:
74:
70:
60:
59:
55:
51:
47:
43:
39:
35:
31:
27:
23:
19:
1335:Graph theory
1313:
1309:
1304:
1293:
1288:
1278:
1273:
1262:
1258:
1253:
1245:(1), 47–56.
1242:
1238:
1233:
1223:
1218:
1210:(1), 23–28.
1207:
1203:
1198:
1188:
1183:
1172:
1168:
1163:
1153:Vol. 9 no. 1
1152:
1148:
1143:
1133:
759:has at most
580:planar graph
453:
429:
287:
94:
76:
68:
66:
46:graph theory
29:
18:graph theory
15:
1316:, 263–277.
975:hyperplanes
424:, which is
300:Turán graph
30:few cliques
1329:Categories
1116:References
1071:for fixed
738:degeneracy
208:such that
90:algorithms
75:, while a
63:Definition
855:≥
820:≡
773:−
616:−
513:−
400:≡
335:⌉
321:⌈
58:clusters.
656:boxicity
293:Examples
73:subgraph
350:has an
42:NP-hard
952:facets
950:whose
899:be an
139:graph
137:vertex
69:clique
26:graphs
22:class
1091:and
879:Let
844:and
716:Any
677:has
634:Any
578:Any
461:tree
298:The
228:has
20:, a
1314:247
997:is
926:in
903:of
827:mod
582:on
535:on
482:on
454:not
407:mod
159:in
36:of
24:of
16:In
1331::
1312:,
1263:23
1261:,
1243:16
1241:,
1206:,
1173:49
1171:,
1151:,
1123:^
619:16
531:A
459:A
67:A
48:,
1208:3
1099:k
1079:d
1059:n
1038:)
1031:1
1028:+
1025:d
1021:k
1017:d
1013:n
1009:(
1005:O
985:G
962:k
934:d
911:n
887:G
864:3
861:+
858:d
852:n
832:3
823:0
817:d
795:3
791:/
787:d
783:3
779:)
776:d
770:n
767:(
747:d
724:n
701:)
696:b
692:n
688:(
685:O
665:b
642:n
613:n
610:8
590:n
563:n
543:n
516:1
510:n
490:n
470:T
440:n
412:3
403:0
397:n
375:3
371:/
367:n
363:3
338:)
332:3
328:/
324:n
318:,
315:n
312:(
309:T
274:X
254:)
251:)
248:n
245:(
242:f
239:(
236:O
216:G
196:)
193:n
190:(
187:f
167:X
147:G
135:-
123:n
103:X
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.