479:
2981:. However, although these graphs have only a polynomial number of cliques to choose among for the cover, having few cliques alone is not enough to make the problem easy: there exist families of graphs with polynomially many cliques for which the intersection number remains NP-hard. The intersection number can also be found in polynomial time for graphs whose maximum degree is five, but is NP-hard for graphs of maximum degree six. On
1329:
it. The competition number is at most equal to the intersection number: one can transform any undirected graph into a competition graph by adding a prey species for each clique in an edge clique cover. However, this relation is not exact, because it is also possible for the predator species to be prey of other species. In a graph with
1328:
of an arbitrary graph represents the smallest number of isolated vertices that could be added to make it into a competition graph. Biologically, if part of a competition graph is observed, then the competition number represents the smallest possible number of unobserved prey species needed to explain
2464:
than the number of edges. In these graphs, the maximum cliques have (with high probability) only a logarithmic number of vertices, implying that this many of them are needed to cover all edges. The tricker part of the bound is proving that it is possible to find enough logarithmically-sized cliques
1142:
of their labels is nonzero. The length of the labels is the intersection number of the graph. This method was used in an early application of intersection numbers, for labeling a set of keywords so that conflicting keywords could be quickly detected, by E. Kellerman of IBM. For this reason, another
1613:
cliques, all of which are either single edges or triangles. An algorithm for finding this cover is simple: remove any two adjacent vertices and inductively cover the remaining graph. Restoring the two removed vertices, cover edges to their shared neighbors by triangles, leaving edges to unshared
2607:
in the graph – two vertices that belong to the same set of cliques have the same neighborhood – and that the graph formed by selecting one vertex per closed neighborhood has the same intersection number as the original graph. Therefore, in polynomial time the input can be reduced to a smaller
1162:
problems in which multiple users of a shared resource should be scheduled for time slots, in such a way that incompatible requests are never scheduled for the same time slot but all pairs of compatible requests are given at least one time slot together. The intersection number of a graph of
1171:
computers, a small clique cover of a graph of incompatible operations can be used to represent their incompatibilities by a small number of artificial resources, allowing resource-based scheduling techniques to be used to assign operations to instruction slots.
2287:
that has two or three degree-2 vertices, and one clique for each vertex that has degree at least two and is not a degree-two vertex of one of these triangles. The intersection number is the number of cliques of these two types.
2897:
by only a polylogarithmic factor. Researchers in this area have also investigated the computational efficiency of heuristics, without guarantees on the solution quality they produce, and their behavior on real-world networks.
2913:, the intersection number may be computed by an algorithm that considers the vertices in an elimination ordering of the graph (an ordering in which each vertex and its later neighbors form a clique) and that, for each vertex
2468:
Much of the early research on intersection numbers involved calculating these numbers on various specific graphs, such as the graphs formed by removing a complete subgraph or a perfect matching from a larger complete graph.
144:
can also be a set of cliques that cover all vertices of a graph. Sometimes "covering" is used in place of "cover". As well as being called the intersection number, the minimum number of these cliques has been called the
1061:
The representation of a graph as an abstract intersection graph of sets can be used to construct more concrete geometric intersection representations of the same graph. In particular, if a graph has intersection number
1202:
that assist in visualizing multiple pairwise comparisons, by assigning a letter or other visual marker for each clique and using these to provide a graphical representation of which variables are indistinguishable.
97:. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of
2429:
1137:
for a graph, in which one labels each vertex by a binary value with a bit for each clique, zero if it does not belong to the clique and one if it belongs. Then two vertices are adjacent if and only if the
1183:, in which one has a 0-1 variable per vertex and a constraint that in each clique of a clique cover the variables sum to at most one. They argue that, for the intersection graphs of paths in certain
402:
and an edge between each two sets that have a nonempty intersection. Every graph can be represented as an intersection graph in this way. The intersection number of the graph is the smallest number
2521:. Therefore, it is also NP-hard to compute the intersection number of a given graph. In turn, the hardness of the intersection number has been used to prove that it is NP-complete to recognize the
2214:. It remains an unsolved problem whether this is true of all claw-free graphs without requiring them to have large independent sets. An important subclass of the claw-free graphs are the
1665:
1781:
1732:
1611:
1550:
1942:
2745:
2097:
1820:
2346:
1187:
communications networks, these intersection numbers are small, explaining the relative ease of solving certain optimization problems in allocating bandwidth on the networks.
271:
639:
444:
400:
372:
344:
316:
3831:
Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf; Piepho, Hans-Peter; Schmid, Ramona (2008), "Algorithms for compact letter displays: Comparison and evaluation",
3751:
Proceedings of the 2000 International
Conference on Compilers, Architectures and Synthesis for Embedded Systems, CASES 2000, San Jose, California, USA, November 7–18, 2000
3749:
Rajagopalan, Subramanian; Vachharajani, Manish; Malik, Sharad (2000), "Handling irregular ILP within conventional VLIW schedulers using artificial resource constraints",
3253:
2462:
2895:
2673:
1218:
is an undirected graph in which the vertices represent species, and edges represent pairs of species that both compete for the same prey. These can be derived from a
67:
1318:
1292:
705:
2839:
2601:
1693:
cliques, maximized when all other vertices are unshared neighbors and the edge between the two vertices must be used as a clique. Adding these two quantities gives
2265:
1988:
1691:
1401:
1373:
1246:
2637:
1783:
edges, for in a triangle-free graph the only optimal clique edge cover has one clique per edge and therefore the intersection number equals the number of edges.
1051:
2971:
2951:
2931:
2859:
2789:
2769:
2574:
2554:
2515:
2495:
2366:
2317:
2285:
2236:
2212:
2192:
2165:
2141:
2117:
2036:
2016:
1962:
1880:
1860:
1840:
1570:
1509:
1489:
1469:
1449:
1347:
1266:
1128:
1100:
1080:
1028:
1008:
988:
968:
948:
928:
908:
885:
865:
845:
825:
805:
785:
765:
745:
725:
679:
659:
615:
575:
555:
528:
504:
464:
420:
221:
201:
123:
87:
3401:
4548:
Proceedings of the 4th
International Conference on the Theory and Applications of Graphs, Western Michigan University, Kalamazoo, Michigan, May 6-9, 1980
2371:
1030:, have a nonempty intersection if and only if there is a clique in the intersection that contains both of them, if and only if there is an edge
3867:
3912:
Proceedings of the 14th
Meeting on Algorithm Engineering & Experiments, ALENEX 2012, The Westin Miyako, Kyoto, Japan, January 16, 2012
2807:
of the graph can find the intersection number in linear time, but simpler algorithms based on finite sets of reduction rules do not work.
2319:
labeled vertices are equally likely (or equivalently, each edge is present or absent, independently of other edges, with probability
597:
The equality of the intersection number and the edge clique cover number is straightforward to prove. In one direction, suppose that
4759:
1415:
networks describing only the pairwise interactions between proteins. More generally, Guillaume and Latapy have argued that, for
4189:
4000:
3927:
3049:
1175:
Shephard and Vetta observe that the intersection number of any network equals the minimum number of constraints needed in an
4218:
3713:
2986:
466:
elements. The problem of finding an intersection representation of a graph with a given number of elements is known as the
4257:
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2016), "Known algorithms for edge clique cover are probably optimal",
2799:
is true then double-exponential dependence is necessary regardless of whether kernelization is used. On graphs of bounded
747:
forms a clique: any two vertices in this subset are adjacent, because their sets have a nonempty intersection containing
1375:
of them can be the prey of more than one other species, so the competition number is at least the intersection number
482:
A graph with intersection number four. The four shaded regions indicate cliques that cover all the edges of the graph.
3766:
3466:
1198:, edge clique covers of a graph representing statistically indistinguishable pairs of variables are used to produce
787:
is contained in one of these cliques: if an edge comes from a non-empty intersection of sets containing an element
3562:
1617:
1412:
4628:
4316:
4172:
Pullman, Norman J. (1983), "Clique coverings of graphs – A survey", in
Reynolds, Louis; Casse, Antoine (eds.),
1180:
4538:(1981), "On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing problems", in
3906:
Blanchette, Mathieu; Kim, Ethan; Vetta, Adrian (2012), "Clique cover on sparse networks", in Bader, David A.;
1155:, but there exist geometric inputs for which this representation requires a near-quadratic number of cliques.
4764:
1745:
1696:
1575:
1514:
534:
3658:; Wong, C. K. (1978), "Covering edges by cliques with regard to keyword conflicts and intersection graphs",
3550:
1885:
4482:
Conte, Alessio; Grossi, Roberto; Marino, Andrea (2020), "Large-scale clique cover of real-world networks",
4057:
3453:
3164:
3080:
2685:
4174:
Combinatorial
Mathematics X: Proceedings of the Conference Held in Adelaide, Australia, August 23-27, 1982
2041:
478:
4401:
3789:
Piepho, Hans-Peter (2004), "An algorithm for a letter-based representation of all-pairwise comparisons",
2901:
More efficient algorithms are known for certain special classes of graphs. The intersection number of an
2796:
2748:
2604:
1789:
3943:
1151:, representations based on the intersection number have been considered as a compact representation for
4115:
2292:
1168:
4754:
4259:
3660:
3458:
2322:
2120:
1107:
278:
226:
4353:
3576:
2194:-vertex claw-free graph has at least three independent vertices, it has intersection number at most
1163:
compatibilities gives the minimum number of time slots needed for such a schedule. In the design of
620:
425:
381:
353:
325:
297:
4584:
2533:
4399:; van Antwerpen-de Fluiter, Babette (2001), "Reduction algorithms for graphs of small treewidth",
1423:
connecting its vertices to the cliques in a clique cover highlights the structure in the network.
3503:
3334:
3162:
Michael, T. S.; Quint, Thomas (2006), "Sphericity, cubicity, and edge clique covers of graphs",
2465:
to cover many edges, allowing the remaining leftover edges to be covered by two-vertex cliques.
2434:
4352:
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michal; Wahlström, Magnus (2014),
4061:
3571:
1219:
1199:
1148:
4311:
2864:
2642:
1491:
of these cliques and together they cover all the edges. It is also true that every graph with
3017:, the NP-hard problem of finding a small number of cliques that cover all vertices of a graph
2973:
is not covered by any earlier clique. It is also possible to find the intersection number in
2144:
507:
98:
34:
4015:
1297:
1271:
684:
4709:
4683:
4649:
4605:
4555:
4513:
4469:
4424:
4339:
4290:
4239:
4199:
4151:
4090:
3970:
3888:
3852:
3810:
3736:
3593:
3526:
3476:
3424:
3365:
3101:
2990:
2817:
2792:
2579:
3118:
2791:
cannot be reduced to single exponential by a kernelization of polynomial size, unless the
2241:
8:
3002:
2811:
2679:
1967:
1739:
1735:
1670:
1380:
1352:
1225:
1176:
4731:
4696:
Hoover, D. N. (1992), "Complexity of graph covering problems for graphs of low degree",
1842:
be the number of pairs of vertices that are not connected by an edge in the given graph
1033:
422:
such that there exists a representation of this type for which the union of the sets in
4609:
4517:
4446:
4441:
4396:
4376:
4294:
4268:
4155:
4129:
4094:
4045:
4023:
3974:
3814:
3772:
3679:
3597:
3369:
3343:
3278:
3229:
3138:
2978:
2956:
2936:
2916:
2844:
2804:
2774:
2754:
2615:
2559:
2539:
2500:
2480:
2351:
2302:
2270:
2221:
2197:
2177:
2150:
2126:
2102:
2021:
2001:
1947:
1865:
1845:
1825:
1555:
1494:
1474:
1454:
1434:
1332:
1251:
1195:
1113:
1085:
1065:
1013:
993:
973:
953:
933:
913:
893:
870:
850:
830:
810:
790:
770:
750:
730:
710:
664:
644:
600:
560:
540:
513:
489:
449:
405:
347:
206:
186:
108:
90:
72:
4626:
Hsu, Wen Lian; Tsai, Kuo-Hui (1991), "Linear time algorithms on circular-arc graphs",
4727:
4641:
4521:
4330:
4185:
3996:
3923:
3818:
3762:
3696:
3498:
3480:
3462:
3316:
3206:
3093:
3045:
4613:
4298:
4098:
3865:
Opsut, Robert J. (1982), "On the computation of the competition number of a graph",
3683:
3373:
3282:
3233:
3142:
1786:
An even tighter bound is possible when the number of edges is strictly greater than
4671:
4637:
4593:
4499:
4491:
4455:
4410:
4380:
4368:
4325:
4278:
4227:
4177:
4159:
4139:
4078:
3978:
3958:
3915:
3876:
3840:
3798:
3776:
3754:
3722:
3669:
3655:
3581:
3512:
3448:
3410:
3353:
3312:
3270:
3221:
3202:
3173:
3130:
3089:
2676:
1991:
1152:
375:
3601:
4705:
4679:
4645:
4601:
4551:
4535:
4509:
4465:
4420:
4335:
4286:
4235:
4195:
4147:
4086:
3966:
3884:
3848:
3806:
3732:
3589:
3522:
3472:
3420:
3361:
3097:
3075:
2171:
1420:
1416:
1408:
1321:
4575:
4539:
4111:
3919:
3844:
3332:
Javadi, Ramin; Hajebi, Sepehr (2019), "Edge clique cover of claw-free graphs",
3300:
2906:
2902:
1134:
531:
319:
4231:
3962:
3177:
4748:
4495:
4213:
4120:
4069:
3484:
3444:
3392:
3261:
3134:
2910:
2609:
4216:(2004), "Recognizing powers of proper interval, split, and chordal graphs",
4049:
4019:
3546:
3517:
3225:
2536:: that is, it can be solved in an amount of time bounded by a polynomial in
2218:, graphs representing edges and touching pairs of edges of some other graph
970:
may be represented by a subset of the cliques, the ones that contain vertex
4543:
4437:
4415:
4053:
3907:
3708:
3704:
3585:
3554:
3014:
2982:
2296:
1995:
585:, and for this reason the intersection number is also sometimes called the
141:
24:
20:
4597:
4460:
4176:, Lecture Notes in Mathematics, vol. 1036, Springer, pp. 72–85,
3802:
3758:
3674:
2985:, computing the intersection number exactly remains NP-hard, but it has a
2556:
multiplied by a larger but computable function of the intersection number
4504:
3488:, Problems GT17 (covering by cliques) and GT59 (intersection graph basis)
3457:, Series of Books in the Mathematical Sciences (1st ed.), New York:
3008:
2974:
2526:
2522:
2518:
1184:
1139:
1103:
4662:
Pullman, Norman J. (1984), "Clique covering of graphs, IV: Algorithms",
4181:
4143:
4082:
3727:
3415:
3274:
3011:, a type of graph characterized by clique edge covers of a special form
3005:, the smallest number of bicliques needed to cover all edges of a graph
2953:
and its later neighbors whenever at least one of the edges incident to
2861:, and the best approximation ratio is known is better than the trivial
2215:
1191:
1159:
160:. The problem of computing the intersection number has been called the
102:
94:
4282:
3454:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
3357:
4736:
4579:
3700:
3303:(1977), "Contentment in graph theory: covering graphs with cliques",
3249:
2800:
4675:
4372:
3880:
3396:
3914:, Society for Industrial and Applied Mathematics, pp. 93–102,
3348:
1207:
1164:
4444:(1994), "On the hardness of approximating minimization problems",
4395:
4354:"Clique cover and graph separation: new incompressibility results"
4273:
4134:
2682:
search procedure over subsets of edges of this kernel gives time
1614:
neighbors as two-vertex cliques. The inductive cover has at most
1407:
Edge clique covers have also been used to infer the existence of
274:
4698:
3254:"Covering graphs by the minimum number of equivalence relations"
2424:{\displaystyle \Theta \left({\frac {n^{2}}{\log ^{2}n}}\right),}
1998:
have small intersection numbers: the intersection number of any
486:
An alternative definition of the intersection number of a graph
3616:
Erratum: Sphericity, cubicity, and edge clique covers of graphs
2909:, which may be computed in polynomial time. More generally, in
1210:
describing predator-prey relationships among animal species, a
4351:
2810:
The problem cannot be approximated in polynomial time with an
2532:
The problem of computing the intersection number is, however,
1248:
in the competition graph whenever there exists a prey species
1143:
name for the problem of computing intersection numbers is the
4314:(1990), "A simple lower bound on edge coverings by cliques",
128:
A set of cliques that cover all edges of a graph is called a
4725:
4582:(1999), "On the fractional intersection number of a graph",
4546:; Goldsmith, D. L.; Lesniak-Foster, L.; Lick, D. R. (eds.),
3748:
4118:(1995), "Covering the edges of a random graph by cliques",
4028:
Proceedings of the
Colloquium held at Tihany, Hungary, 1966
3711:(1994), "Can visibility graphs be represented compactly?",
3628:
Kellerman, E. (1973), "Determination of keyword conflict",
3830:
3200:
69:
is the smallest number of elements in a representation of
3753:, Association for Computing Machinery, pp. 157–164,
1667:
cliques, and the two removed vertices contribute at most
4044:
2576:. This may be shown by observing that there are at most
1222:
representing predator-prey relations by drawing an edge
4256:
3993:
Schaum's
Outline of Theory and Problems of Graph Theory
3501:(1945), "Sur deux propriétés des classes d'ensembles",
3402:
3207:"Data reduction and exact algorithms for clique cover"
2618:
2327:
1794:
3695:
3078:(1985), "Applications of edge coverings by cliques",
2959:
2939:
2919:
2867:
2847:
2820:
2777:
2757:
2688:
2645:
2582:
2562:
2542:
2503:
2483:
2437:
2374:
2354:
2325:
2305:
2273:
2244:
2224:
2200:
2180:
2153:
2129:
2105:
2044:
2024:
2004:
1970:
1950:
1888:
1868:
1848:
1828:
1792:
1748:
1699:
1673:
1620:
1578:
1558:
1517:
1497:
1477:
1471:. Each edge is itself a two-vertex clique. There are
1457:
1437:
1383:
1355:
1335:
1300:
1274:
1268:
such that the predator-prey relation graph has edges
1254:
1228:
1116:
1088:
1068:
1036:
1016:
996:
976:
956:
936:
916:
896:
873:
853:
833:
813:
793:
773:
753:
733:
713:
687:
667:
647:
623:
603:
563:
543:
516:
492:
452:
428:
408:
384:
356:
328:
300:
229:
209:
189:
111:
75:
37:
3555:"The representation of a graph by set intersections"
3497:
1082:, it can be represented as an intersection graph of
577:. A set of cliques with this property is known as a
2267:may be formed with one clique for each triangle in
3905:
2965:
2945:
2925:
2889:
2853:
2833:
2783:
2763:
2739:
2667:
2631:
2595:
2568:
2548:
2509:
2489:
2456:
2423:
2360:
2340:
2311:
2279:
2259:
2230:
2206:
2186:
2159:
2135:
2111:
2091:
2030:
2010:
1982:
1956:
1936:
1874:
1854:
1834:
1814:
1775:
1726:
1685:
1659:
1605:
1564:
1544:
1503:
1483:
1463:
1443:
1395:
1367:
1341:
1312:
1286:
1260:
1240:
1122:
1094:
1074:
1045:
1022:
1002:
982:
962:
942:
922:
902:
879:
859:
839:
819:
799:
779:
759:
739:
719:
699:
673:
653:
633:
609:
569:
549:
522:
498:
458:
438:
414:
394:
366:
338:
310:
265:
215:
195:
117:
81:
61:
4481:
4062:"Clique coverings of the edges of a random graph"
3791:Journal of Computational and Graphical Statistics
3653:
3639:
2170:It follows from deep results on the structure of
1411:, systems of mutually interacting proteins, from
1320:. Every competition graph must have at least one
4746:
4574:
3545:
3123:IEEE Journal on Selected Areas in Communications
807:, then that edge is contained in the clique for
230:
3942:Guillaume, Jean-Loup; Latapy, Matthieu (2004),
3941:
3397:"Complexity results on graphs with few cliques"
2497:has intersection number at most a given number
4436:
3868:SIAM Journal on Algebraic and Discrete Methods
2368:-vertex random graph is with high probability
3944:"Bipartite structure of all complex networks"
3390:
3116:
4533:
3990:
3833:Computational Statistics & Data Analysis
3613:
3443:
3331:
3161:
2238:. An optimal clique cover of the line graph
1770:
1749:
1721:
1700:
1654:
1621:
1600:
1579:
1539:
1518:
3117:Shepherd, F.B.; Vetta, A. (November 2004),
3039:
2472:
1660:{\displaystyle \lfloor (n-2)^{2}/4\rfloor }
4211:
4110:
557:) that together cover all of the edges of
4503:
4459:
4414:
4329:
4272:
4133:
3726:
3673:
3627:
3575:
3516:
3414:
3347:
1511:vertices has intersection number at most
1419:of all types, replacing the network by a
1158:Another class of applications comes from
1053:included in one of the covering cliques.
990:. Two of these subsets, for two vertices
140:, although the last term is ambiguous: a
4252:
4250:
4248:
3995:, McGraw-Hill Professional, p. 40,
3901:
3899:
3897:
3824:
3649:
3647:
3541:
3539:
3537:
3535:
3201:Gramm, Jens; Guo, Jiong; Hüffner, Falk;
3196:
3194:
3192:
3190:
3188:
3186:
3040:Gross, Jonathan L.; Yellen, Jay (2006),
1572:-vertex graph can be covered by at most
1179:formulation of the problem of computing
1133:A clique cover can be used as a kind of
477:
4661:
4625:
4570:
4568:
4560:
4391:
4389:
4345:
4310:
4171:
4033:
3439:
3437:
3435:
3433:
3157:
3155:
3153:
3151:
3074:
2771:. The double-exponential dependence on
1776:{\displaystyle \lfloor n^{2}/4\rfloor }
1727:{\displaystyle \lfloor n^{2}/4\rfloor }
1606:{\displaystyle \lfloor n^{2}/4\rfloor }
1545:{\displaystyle \lfloor n^{2}/4\rfloor }
16:Fewest cliques covering a graph's edges
4747:
4695:
4361:ACM Transactions on Computation Theory
4038:
4014:
3788:
3689:
3614:Michael, T. S.; Quint, Thomas (2009),
3386:
3384:
3382:
3327:
3325:
3112:
3110:
3035:
3033:
3031:
1937:{\displaystyle (t-1)t\leq p<t(t+1)}
1451:edges has intersection number at most
617:is the intersection graph of a family
289:
223:edges has intersection number at most
4726:
4550:, New York: Wiley, pp. 479–492,
4475:
4245:
3894:
3864:
3742:
3714:Discrete & Computational Geometry
3644:
3607:
3532:
3299:
3295:
3293:
3291:
3244:
3242:
3183:
3070:
3068:
3066:
3064:
3062:
3060:
2740:{\displaystyle 2^{O(4^{k})}+n^{O(1)}}
506:is that it is the smallest number of
473:
4619:
4565:
4527:
4430:
4386:
4219:SIAM Journal on Discrete Mathematics
4205:
4104:
4018:(1968), "On covering of graphs", in
3935:
3491:
3430:
3248:
3214:Journal of Experimental Algorithmics
3148:
2987:polynomial-time approximation scheme
2092:{\displaystyle 2e^{2}(d+1)^{2}\ln n}
1552:. More strongly, the edges of every
4689:
4655:
4304:
4165:
4008:
3984:
3858:
3782:
3621:
3379:
3322:
3119:"Lighting fibers in a dark network"
3107:
3028:
1815:{\displaystyle {\tfrac {n^{2}}{4}}}
890:In the other direction, if a graph
727:corresponding to sets that contain
13:
4030:, Academic Press, pp. 231–236
3288:
3239:
3057:
2375:
1944:. Then the intersection number of
626:
431:
387:
378:that has a vertex for each set in
359:
331:
303:
14:
4776:
4719:
3640:Kou, Stockmeyer & Wong (1978)
3630:IBM Technical Disclosure Bulletin
3042:Graph Theory and its Applications
2905:is always equal to its number of
2348:) the intersection number of an
1882:be the unique integer for which
1734:cliques total. This generalizes
468:intersection graph basis problem
166:intersection graph basis problem
3563:Canadian Journal of Mathematics
2341:{\displaystyle {\tfrac {1}{2}}}
1426:
1056:
681:elements. Then for any element
277:to compute or approximate, but
266:{\displaystyle \min(m,n^{2}/4)}
4760:Intersection classes of graphs
4629:Information Processing Letters
3951:Information Processing Letters
2884:
2871:
2732:
2726:
2710:
2697:
2662:
2649:
2477:Testing whether a given graph
2254:
2248:
2071:
2058:
1931:
1919:
1901:
1889:
1637:
1624:
1304:
1278:
634:{\displaystyle {\mathcal {F}}}
592:
439:{\displaystyle {\mathcal {F}}}
395:{\displaystyle {\mathcal {F}}}
367:{\displaystyle {\mathcal {F}}}
339:{\displaystyle {\mathcal {F}}}
311:{\displaystyle {\mathcal {F}}}
284:
260:
233:
56:
44:
1:
3021:
2121:base of the natural logarithm
273:. The intersection number is
4642:10.1016/0020-0190(91)90165-E
4331:10.1016/0012-365X(90)90168-H
3991:Balakrishnan, V. K. (1997),
3499:Szpilrajn-Marczewski, Edward
3317:10.1016/1385-7258(77)90055-5
3165:Discrete Applied Mathematics
3094:10.1016/0166-218X(85)90061-7
3081:Discrete Applied Mathematics
867:cliques, one per element of
707:, the subset of vertices of
7:
4484:Information and Computation
4402:Information and Computation
2996:
2803:, dynamic programming on a
2797:exponential time hypothesis
2147:of the complement graph of
1413:protein–protein interaction
162:intersection number problem
10:
4781:
3920:10.1137/1.9781611972924.10
3845:10.1016/j.csda.2006.09.035
3044:, CRC Press, p. 440,
2457:{\displaystyle \log ^{2}n}
1169:very long instruction word
1135:adjacency labelling scheme
930:cliques, then each vertex
827:. Therefore, the edges of
4664:SIAM Journal on Computing
4260:SIAM Journal on Computing
4232:10.1137/S0895480103425930
3963:10.1016/j.ipl.2004.03.007
3661:Communications of the ACM
3459:W. H. Freeman and Company
3305:Indagationes Mathematicae
3178:10.1016/j.dam.2006.01.004
2534:fixed-parameter tractable
2299:, in which all graphs on
2293:Erdős–Rényi–Gilbert model
767:. Further, every edge in
346:to be repeated. Then the
279:fixed-parameter tractable
174:edge clique cover problem
4585:Graphs and Combinatorics
4496:10.1016/j.ic.2019.104464
4490:, Article 104464, 15pp,
3135:10.1109/jsac.2004.833850
2890:{\displaystyle O(n^{2})}
2668:{\displaystyle O(4^{k})}
2473:Computational complexity
1431:Trivially, a graph with
1181:maximum independent sets
1145:keyword conflict problem
587:edge clique cover number
178:keyword conflict problem
154:edge clique cover number
3518:10.4064/fm-33-1-303-307
3504:Fundamenta Mathematicae
3335:Journal of Graph Theory
3226:10.1145/1412228.1412236
2431:smaller by a factor of
2174:that, when a connected
1200:compact letter displays
62:{\displaystyle G=(V,E)}
4576:Scheinerman, Edward R.
4416:10.1006/inco.2000.2958
3586:10.4153/CJM-1966-014-3
2967:
2947:
2927:
2891:
2855:
2835:
2795:collapses, and if the
2785:
2765:
2741:
2669:
2633:
2597:
2570:
2550:
2511:
2491:
2458:
2425:
2362:
2342:
2313:
2281:
2261:
2232:
2208:
2188:
2161:
2137:
2113:
2093:
2032:
2012:
1990:. Graphs that are the
1984:
1958:
1938:
1876:
1856:
1836:
1816:
1777:
1728:
1687:
1661:
1607:
1566:
1546:
1505:
1485:
1465:
1445:
1397:
1369:
1343:
1314:
1313:{\displaystyle v\to w}
1288:
1287:{\displaystyle u\to w}
1262:
1242:
1220:directed acyclic graph
1149:computational geometry
1124:
1096:
1076:
1047:
1024:
1004:
984:
964:
944:
924:
904:
881:
861:
841:
821:
801:
781:
761:
741:
721:
701:
700:{\displaystyle x\in U}
675:
655:
635:
611:
571:
551:
524:
500:
483:
460:
440:
416:
396:
368:
340:
312:
267:
217:
197:
119:
83:
63:
4732:"Intersection Number"
4598:10.1007/s003730050068
4461:10.1145/185675.306789
3803:10.1198/1061860043515
3759:10.1145/354880.354902
3675:10.1145/359340.359346
2968:
2948:
2933:, forms a clique for
2928:
2892:
2856:
2836:
2834:{\displaystyle n^{c}}
2786:
2766:
2742:
2670:
2634:
2598:
2596:{\displaystyle 2^{k}}
2571:
2551:
2512:
2492:
2459:
2426:
2363:
2343:
2314:
2282:
2262:
2233:
2209:
2189:
2162:
2138:
2114:
2094:
2033:
2013:
1985:
1959:
1939:
1877:
1857:
1837:
1817:
1778:
1729:
1688:
1662:
1608:
1567:
1547:
1506:
1486:
1466:
1446:
1398:
1370:
1344:
1315:
1289:
1263:
1243:
1125:
1097:
1077:
1048:
1025:
1005:
985:
965:
945:
925:
905:
882:
862:
842:
822:
802:
782:
762:
742:
722:
702:
676:
656:
636:
612:
572:
552:
525:
501:
481:
461:
441:
417:
397:
369:
341:
313:
268:
218:
198:
120:
84:
64:
4765:NP-complete problems
4317:Discrete Mathematics
2957:
2937:
2917:
2865:
2845:
2841:, for some constant
2818:
2793:polynomial hierarchy
2775:
2755:
2686:
2643:
2616:
2605:closed neighborhoods
2580:
2560:
2540:
2501:
2481:
2435:
2372:
2352:
2323:
2303:
2271:
2260:{\displaystyle L(G)}
2242:
2222:
2198:
2178:
2151:
2127:
2103:
2042:
2022:
2002:
1968:
1948:
1886:
1866:
1846:
1826:
1790:
1746:
1697:
1671:
1618:
1576:
1556:
1515:
1495:
1475:
1455:
1435:
1381:
1353:
1333:
1298:
1272:
1252:
1226:
1114:
1086:
1066:
1034:
1014:
994:
974:
954:
934:
914:
894:
871:
851:
831:
811:
791:
771:
751:
731:
711:
685:
665:
645:
641:of sets whose union
621:
601:
561:
541:
514:
490:
450:
426:
406:
382:
354:
326:
298:
227:
207:
187:
109:
105:all of the edges of
73:
35:
4442:Yannakakis, Mihalis
4397:Bodlaender, Hans L.
3003:Bipartite dimension
2979:circular-arc graphs
2812:approximation ratio
2680:dynamic programming
2675:edges. Applying an
1983:{\displaystyle p+t}
1740:triangle-free graph
1686:{\displaystyle n-1}
1396:{\displaystyle n-2}
1368:{\displaystyle n-2}
1241:{\displaystyle u-v}
1216:niche overlap graph
1206:In the analysis of
1177:integer programming
322:, allowing sets in
290:Intersection graphs
170:covering by cliques
158:clique cover number
29:intersection number
4728:Weisstein, Eric W.
4447:Journal of the ACM
4182:10.1007/bfb0071509
4144:10.1007/BF01192522
4083:10.1007/BF01202786
3728:10.1007/BF02574385
3549:; Goodman, A. W.;
3416:10.46298/dmtcs.387
3275:10.1007/bf02579381
2963:
2943:
2923:
2887:
2851:
2831:
2805:tree decomposition
2781:
2761:
2749:double exponential
2737:
2665:
2632:{\textstyle 2^{k}}
2629:
2593:
2566:
2546:
2507:
2487:
2454:
2421:
2358:
2338:
2336:
2309:
2277:
2257:
2228:
2204:
2184:
2157:
2133:
2109:
2089:
2028:
2008:
1980:
1954:
1934:
1872:
1852:
1832:
1812:
1810:
1773:
1724:
1683:
1657:
1603:
1562:
1542:
1501:
1481:
1461:
1441:
1393:
1365:
1349:vertices, at most
1339:
1326:competition number
1310:
1284:
1258:
1238:
1196:data visualization
1120:
1102:-dimensional unit
1092:
1072:
1046:{\displaystyle uv}
1043:
1020:
1000:
980:
960:
940:
920:
910:can be covered by
900:
877:
857:
847:can be covered by
837:
817:
797:
777:
757:
737:
717:
697:
671:
651:
631:
607:
567:
547:
520:
496:
484:
474:Clique edge covers
456:
436:
412:
392:
364:
348:intersection graph
336:
308:
263:
213:
193:
115:
91:intersection graph
79:
59:
4283:10.1137/130947076
4214:Corneil, Derek G.
4191:978-3-540-12708-6
4002:978-0-07-005489-9
3929:978-1-61197-212-2
3656:Stockmeyer, L. J.
3449:Johnson, David S.
3445:Garey, Michael R.
3358:10.1002/jgt.22403
3203:Niedermeier, Rolf
3051:978-1-58488-505-4
2991:Baker's technique
2966:{\displaystyle v}
2946:{\displaystyle v}
2926:{\displaystyle v}
2854:{\displaystyle c}
2784:{\displaystyle k}
2764:{\displaystyle k}
2569:{\displaystyle k}
2549:{\displaystyle n}
2510:{\displaystyle k}
2490:{\displaystyle G}
2412:
2361:{\displaystyle n}
2335:
2312:{\displaystyle n}
2280:{\displaystyle G}
2231:{\displaystyle G}
2207:{\displaystyle n}
2187:{\displaystyle n}
2160:{\displaystyle G}
2136:{\displaystyle d}
2112:{\displaystyle e}
2031:{\displaystyle G}
2011:{\displaystyle n}
1957:{\displaystyle G}
1875:{\displaystyle t}
1855:{\displaystyle G}
1835:{\displaystyle p}
1809:
1565:{\displaystyle n}
1504:{\displaystyle n}
1484:{\displaystyle m}
1464:{\displaystyle m}
1444:{\displaystyle m}
1409:protein complexes
1342:{\displaystyle n}
1261:{\displaystyle w}
1212:competition graph
1153:visibility graphs
1123:{\displaystyle k}
1095:{\displaystyle k}
1075:{\displaystyle k}
1023:{\displaystyle v}
1003:{\displaystyle u}
983:{\displaystyle v}
963:{\displaystyle G}
943:{\displaystyle v}
923:{\displaystyle k}
903:{\displaystyle G}
880:{\displaystyle U}
860:{\displaystyle k}
840:{\displaystyle G}
820:{\displaystyle y}
800:{\displaystyle y}
780:{\displaystyle G}
760:{\displaystyle x}
740:{\displaystyle x}
720:{\displaystyle G}
674:{\displaystyle k}
654:{\displaystyle U}
610:{\displaystyle G}
583:edge clique cover
579:clique edge cover
570:{\displaystyle G}
550:{\displaystyle G}
523:{\displaystyle G}
499:{\displaystyle G}
459:{\displaystyle k}
415:{\displaystyle k}
216:{\displaystyle m}
196:{\displaystyle n}
183:Every graph with
136:, or even just a
134:edge clique cover
130:clique edge cover
118:{\displaystyle G}
82:{\displaystyle G}
4772:
4755:Graph invariants
4741:
4740:
4713:
4712:
4693:
4687:
4686:
4659:
4653:
4652:
4623:
4617:
4616:
4572:
4563:
4558:
4531:
4525:
4524:
4507:
4479:
4473:
4472:
4463:
4434:
4428:
4427:
4418:
4393:
4384:
4383:
4358:
4349:
4343:
4342:
4333:
4308:
4302:
4301:
4276:
4254:
4243:
4242:
4209:
4203:
4202:
4169:
4163:
4162:
4137:
4108:
4102:
4101:
4066:
4058:West, Douglas B.
4042:
4036:
4031:
4012:
4006:
4005:
3988:
3982:
3981:
3948:
3939:
3933:
3932:
3903:
3892:
3891:
3862:
3856:
3855:
3828:
3822:
3821:
3786:
3780:
3779:
3746:
3740:
3739:
3730:
3693:
3687:
3686:
3677:
3651:
3642:
3637:
3625:
3619:
3618:
3611:
3605:
3604:
3579:
3559:
3543:
3530:
3529:
3520:
3495:
3489:
3487:
3441:
3428:
3427:
3418:
3388:
3377:
3376:
3351:
3329:
3320:
3319:
3297:
3286:
3285:
3258:
3246:
3237:
3236:
3211:
3198:
3181:
3180:
3172:(8): 1309–1313,
3159:
3146:
3145:
3129:(9): 1583–1588,
3114:
3105:
3104:
3076:Roberts, Fred S.
3072:
3055:
3054:
3037:
2972:
2970:
2969:
2964:
2952:
2950:
2949:
2944:
2932:
2930:
2929:
2924:
2896:
2894:
2893:
2888:
2883:
2882:
2860:
2858:
2857:
2852:
2840:
2838:
2837:
2832:
2830:
2829:
2790:
2788:
2787:
2782:
2770:
2768:
2767:
2762:
2746:
2744:
2743:
2738:
2736:
2735:
2714:
2713:
2709:
2708:
2677:exponential time
2674:
2672:
2671:
2666:
2661:
2660:
2638:
2636:
2635:
2630:
2628:
2627:
2602:
2600:
2599:
2594:
2592:
2591:
2575:
2573:
2572:
2567:
2555:
2553:
2552:
2547:
2516:
2514:
2513:
2508:
2496:
2494:
2493:
2488:
2463:
2461:
2460:
2455:
2447:
2446:
2430:
2428:
2427:
2422:
2417:
2413:
2411:
2404:
2403:
2393:
2392:
2383:
2367:
2365:
2364:
2359:
2347:
2345:
2344:
2339:
2337:
2328:
2318:
2316:
2315:
2310:
2286:
2284:
2283:
2278:
2266:
2264:
2263:
2258:
2237:
2235:
2234:
2229:
2213:
2211:
2210:
2205:
2193:
2191:
2190:
2185:
2172:claw-free graphs
2166:
2164:
2163:
2158:
2142:
2140:
2139:
2134:
2118:
2116:
2115:
2110:
2098:
2096:
2095:
2090:
2079:
2078:
2057:
2056:
2037:
2035:
2034:
2029:
2017:
2015:
2014:
2009:
1989:
1987:
1986:
1981:
1963:
1961:
1960:
1955:
1943:
1941:
1940:
1935:
1881:
1879:
1878:
1873:
1861:
1859:
1858:
1853:
1841:
1839:
1838:
1833:
1821:
1819:
1818:
1813:
1811:
1805:
1804:
1795:
1782:
1780:
1779:
1774:
1766:
1761:
1760:
1736:Mantel's theorem
1733:
1731:
1730:
1725:
1717:
1712:
1711:
1692:
1690:
1689:
1684:
1666:
1664:
1663:
1658:
1650:
1645:
1644:
1612:
1610:
1609:
1604:
1596:
1591:
1590:
1571:
1569:
1568:
1563:
1551:
1549:
1548:
1543:
1535:
1530:
1529:
1510:
1508:
1507:
1502:
1490:
1488:
1487:
1482:
1470:
1468:
1467:
1462:
1450:
1448:
1447:
1442:
1417:complex networks
1404:
1402:
1400:
1399:
1394:
1374:
1372:
1371:
1366:
1348:
1346:
1345:
1340:
1319:
1317:
1316:
1311:
1293:
1291:
1290:
1285:
1267:
1265:
1264:
1259:
1247:
1245:
1244:
1239:
1147:. Similarly, in
1129:
1127:
1126:
1121:
1101:
1099:
1098:
1093:
1081:
1079:
1078:
1073:
1052:
1050:
1049:
1044:
1029:
1027:
1026:
1021:
1009:
1007:
1006:
1001:
989:
987:
986:
981:
969:
967:
966:
961:
949:
947:
946:
941:
929:
927:
926:
921:
909:
907:
906:
901:
886:
884:
883:
878:
866:
864:
863:
858:
846:
844:
843:
838:
826:
824:
823:
818:
806:
804:
803:
798:
786:
784:
783:
778:
766:
764:
763:
758:
746:
744:
743:
738:
726:
724:
723:
718:
706:
704:
703:
698:
680:
678:
677:
672:
660:
658:
657:
652:
640:
638:
637:
632:
630:
629:
616:
614:
613:
608:
576:
574:
573:
568:
556:
554:
553:
548:
529:
527:
526:
521:
505:
503:
502:
497:
465:
463:
462:
457:
445:
443:
442:
437:
435:
434:
421:
419:
418:
413:
401:
399:
398:
393:
391:
390:
376:undirected graph
373:
371:
370:
365:
363:
362:
345:
343:
342:
337:
335:
334:
317:
315:
314:
309:
307:
306:
272:
270:
269:
264:
256:
251:
250:
222:
220:
219:
214:
202:
200:
199:
194:
124:
122:
121:
116:
88:
86:
85:
80:
68:
66:
65:
60:
4780:
4779:
4775:
4774:
4773:
4771:
4770:
4769:
4745:
4744:
4722:
4717:
4716:
4694:
4690:
4676:10.1137/0213005
4660:
4656:
4624:
4620:
4573:
4566:
4532:
4528:
4480:
4476:
4435:
4431:
4394:
4387:
4373:10.1145/2594439
4367:(2): 6:1–6:19,
4356:
4350:
4346:
4309:
4305:
4255:
4246:
4210:
4206:
4192:
4170:
4166:
4109:
4105:
4064:
4043:
4039:
4013:
4009:
4003:
3989:
3985:
3946:
3940:
3936:
3930:
3904:
3895:
3881:10.1137/0603043
3863:
3859:
3829:
3825:
3787:
3783:
3769:
3747:
3743:
3694:
3690:
3652:
3645:
3626:
3622:
3612:
3608:
3577:10.1.1.210.6950
3557:
3544:
3533:
3496:
3492:
3469:
3442:
3431:
3389:
3380:
3330:
3323:
3298:
3289:
3256:
3247:
3240:
3209:
3199:
3184:
3160:
3149:
3115:
3108:
3073:
3058:
3052:
3038:
3029:
3024:
2999:
2958:
2955:
2954:
2938:
2935:
2934:
2918:
2915:
2914:
2907:maximal cliques
2878:
2874:
2866:
2863:
2862:
2846:
2843:
2842:
2825:
2821:
2819:
2816:
2815:
2776:
2773:
2772:
2756:
2753:
2752:
2722:
2718:
2704:
2700:
2693:
2689:
2687:
2684:
2683:
2656:
2652:
2644:
2641:
2640:
2623:
2619:
2617:
2614:
2613:
2587:
2583:
2581:
2578:
2577:
2561:
2558:
2557:
2541:
2538:
2537:
2502:
2499:
2498:
2482:
2479:
2478:
2475:
2442:
2438:
2436:
2433:
2432:
2399:
2395:
2394:
2388:
2384:
2382:
2378:
2373:
2370:
2369:
2353:
2350:
2349:
2326:
2324:
2321:
2320:
2304:
2301:
2300:
2272:
2269:
2268:
2243:
2240:
2239:
2223:
2220:
2219:
2199:
2196:
2195:
2179:
2176:
2175:
2152:
2149:
2148:
2143:is the maximum
2128:
2125:
2124:
2104:
2101:
2100:
2074:
2070:
2052:
2048:
2043:
2040:
2039:
2023:
2020:
2019:
2003:
2000:
1999:
1969:
1966:
1965:
1949:
1946:
1945:
1887:
1884:
1883:
1867:
1864:
1863:
1847:
1844:
1843:
1827:
1824:
1823:
1800:
1796:
1793:
1791:
1788:
1787:
1762:
1756:
1752:
1747:
1744:
1743:
1713:
1707:
1703:
1698:
1695:
1694:
1672:
1669:
1668:
1646:
1640:
1636:
1619:
1616:
1615:
1592:
1586:
1582:
1577:
1574:
1573:
1557:
1554:
1553:
1531:
1525:
1521:
1516:
1513:
1512:
1496:
1493:
1492:
1476:
1473:
1472:
1456:
1453:
1452:
1436:
1433:
1432:
1429:
1421:bipartite graph
1382:
1379:
1378:
1376:
1354:
1351:
1350:
1334:
1331:
1330:
1322:isolated vertex
1299:
1296:
1295:
1273:
1270:
1269:
1253:
1250:
1249:
1227:
1224:
1223:
1115:
1112:
1111:
1087:
1084:
1083:
1067:
1064:
1063:
1059:
1035:
1032:
1031:
1015:
1012:
1011:
995:
992:
991:
975:
972:
971:
955:
952:
951:
935:
932:
931:
915:
912:
911:
895:
892:
891:
872:
869:
868:
852:
849:
848:
832:
829:
828:
812:
809:
808:
792:
789:
788:
772:
769:
768:
752:
749:
748:
732:
729:
728:
712:
709:
708:
686:
683:
682:
666:
663:
662:
646:
643:
642:
625:
624:
622:
619:
618:
602:
599:
598:
595:
562:
559:
558:
542:
539:
538:
515:
512:
511:
491:
488:
487:
476:
451:
448:
447:
430:
429:
427:
424:
423:
407:
404:
403:
386:
385:
383:
380:
379:
358:
357:
355:
352:
351:
330:
329:
327:
324:
323:
302:
301:
299:
296:
295:
292:
287:
252:
246:
242:
228:
225:
224:
208:
205:
204:
188:
185:
184:
110:
107:
106:
74:
71:
70:
36:
33:
32:
17:
12:
11:
5:
4778:
4768:
4767:
4762:
4757:
4743:
4742:
4721:
4720:External links
4718:
4715:
4714:
4688:
4654:
4636:(3): 123–129,
4618:
4592:(3): 341–351,
4564:
4561:Roberts (1985)
4559:; as cited by
4536:Roberts, F. S.
4534:Opsut, R. J.;
4526:
4474:
4454:(5): 960–981,
4429:
4385:
4344:
4324:(1): 103–104,
4303:
4244:
4212:Lau, Lap Chi;
4204:
4190:
4164:
4128:(4): 489–497,
4103:
4046:Bollobás, Béla
4037:
4034:Roberts (1985)
4032:; as cited by
4007:
4001:
3983:
3957:(5): 215–221,
3934:
3928:
3893:
3875:(4): 420–428,
3857:
3839:(2): 725–736,
3823:
3797:(2): 456–466,
3781:
3767:
3741:
3721:(3): 347–365,
3697:Agarwal, P. K.
3688:
3668:(2): 135–139,
3643:
3638:, as cited by
3620:
3606:
3570:(1): 106–112,
3531:
3490:
3467:
3429:
3409:(1): 127–135,
3393:Stewart, Lorna
3391:Rosgen, Bill;
3378:
3342:(3): 311–405,
3321:
3311:(5): 406–424,
3287:
3269:(3): 201–206,
3238:
3182:
3147:
3106:
3056:
3050:
3026:
3025:
3023:
3020:
3019:
3018:
3012:
3006:
2998:
2995:
2962:
2942:
2922:
2911:chordal graphs
2903:interval graph
2886:
2881:
2877:
2873:
2870:
2850:
2828:
2824:
2780:
2760:
2734:
2731:
2728:
2725:
2721:
2717:
2712:
2707:
2703:
2699:
2696:
2692:
2664:
2659:
2655:
2651:
2648:
2626:
2622:
2590:
2586:
2565:
2545:
2506:
2486:
2474:
2471:
2453:
2450:
2445:
2441:
2420:
2416:
2410:
2407:
2402:
2398:
2391:
2387:
2381:
2377:
2357:
2334:
2331:
2308:
2276:
2256:
2253:
2250:
2247:
2227:
2203:
2183:
2156:
2132:
2108:
2088:
2085:
2082:
2077:
2073:
2069:
2066:
2063:
2060:
2055:
2051:
2047:
2027:
2018:-vertex graph
2007:
1979:
1976:
1973:
1953:
1933:
1930:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1894:
1891:
1871:
1851:
1831:
1808:
1803:
1799:
1772:
1769:
1765:
1759:
1755:
1751:
1723:
1720:
1716:
1710:
1706:
1702:
1682:
1679:
1676:
1656:
1653:
1649:
1643:
1639:
1635:
1632:
1629:
1626:
1623:
1602:
1599:
1595:
1589:
1585:
1581:
1561:
1541:
1538:
1534:
1528:
1524:
1520:
1500:
1480:
1460:
1440:
1428:
1425:
1392:
1389:
1386:
1364:
1361:
1358:
1338:
1309:
1306:
1303:
1283:
1280:
1277:
1257:
1237:
1234:
1231:
1119:
1091:
1071:
1058:
1055:
1042:
1039:
1019:
999:
979:
959:
939:
919:
899:
876:
856:
836:
816:
796:
776:
756:
736:
716:
696:
693:
690:
670:
650:
628:
606:
594:
591:
566:
546:
519:
495:
475:
472:
455:
433:
411:
389:
361:
333:
320:family of sets
305:
291:
288:
286:
283:
262:
259:
255:
249:
245:
241:
238:
235:
232:
212:
192:
114:
78:
58:
55:
52:
49:
46:
43:
40:
15:
9:
6:
4:
3:
2:
4777:
4766:
4763:
4761:
4758:
4756:
4753:
4752:
4750:
4739:
4738:
4733:
4729:
4724:
4723:
4711:
4707:
4703:
4699:
4692:
4685:
4681:
4677:
4673:
4669:
4665:
4658:
4651:
4647:
4643:
4639:
4635:
4631:
4630:
4622:
4615:
4611:
4607:
4603:
4599:
4595:
4591:
4587:
4586:
4581:
4580:Trenk, Ann N.
4577:
4571:
4569:
4562:
4557:
4553:
4549:
4545:
4541:
4540:Chartrand, G.
4537:
4530:
4523:
4519:
4515:
4511:
4506:
4505:11568/1028251
4501:
4497:
4493:
4489:
4485:
4478:
4471:
4467:
4462:
4457:
4453:
4449:
4448:
4443:
4439:
4438:Lund, Carsten
4433:
4426:
4422:
4417:
4412:
4409:(2): 86–119,
4408:
4404:
4403:
4398:
4392:
4390:
4382:
4378:
4374:
4370:
4366:
4362:
4355:
4348:
4341:
4337:
4332:
4327:
4323:
4319:
4318:
4313:
4307:
4300:
4296:
4292:
4288:
4284:
4280:
4275:
4270:
4266:
4262:
4261:
4253:
4251:
4249:
4241:
4237:
4233:
4229:
4226:(1): 83–102,
4225:
4221:
4220:
4215:
4208:
4201:
4197:
4193:
4187:
4183:
4179:
4175:
4168:
4161:
4157:
4153:
4149:
4145:
4141:
4136:
4131:
4127:
4123:
4122:
4121:Combinatorica
4117:
4113:
4107:
4100:
4096:
4092:
4088:
4084:
4080:
4076:
4072:
4071:
4070:Combinatorica
4063:
4059:
4055:
4054:Spencer, Joel
4051:
4047:
4041:
4035:
4029:
4025:
4021:
4017:
4011:
4004:
3998:
3994:
3987:
3980:
3976:
3972:
3968:
3964:
3960:
3956:
3952:
3945:
3938:
3931:
3925:
3921:
3917:
3913:
3909:
3908:Mutzel, Petra
3902:
3900:
3898:
3890:
3886:
3882:
3878:
3874:
3870:
3869:
3861:
3854:
3850:
3846:
3842:
3838:
3834:
3827:
3820:
3816:
3812:
3808:
3804:
3800:
3796:
3792:
3785:
3778:
3774:
3770:
3768:1-58113-338-3
3764:
3760:
3756:
3752:
3745:
3738:
3734:
3729:
3724:
3720:
3716:
3715:
3710:
3706:
3702:
3698:
3692:
3685:
3681:
3676:
3671:
3667:
3663:
3662:
3657:
3650:
3648:
3641:
3635:
3631:
3624:
3617:
3610:
3603:
3599:
3595:
3591:
3587:
3583:
3578:
3573:
3569:
3565:
3564:
3556:
3552:
3548:
3542:
3540:
3538:
3536:
3528:
3524:
3519:
3514:
3510:
3507:(in French),
3506:
3505:
3500:
3494:
3486:
3482:
3478:
3474:
3470:
3468:9780716710455
3464:
3460:
3456:
3455:
3450:
3446:
3440:
3438:
3436:
3434:
3426:
3422:
3417:
3412:
3408:
3404:
3403:
3398:
3394:
3387:
3385:
3383:
3375:
3371:
3367:
3363:
3359:
3355:
3350:
3345:
3341:
3337:
3336:
3328:
3326:
3318:
3314:
3310:
3306:
3302:
3296:
3294:
3292:
3284:
3280:
3276:
3272:
3268:
3264:
3263:
3262:Combinatorica
3255:
3251:
3245:
3243:
3235:
3231:
3227:
3223:
3219:
3215:
3208:
3204:
3197:
3195:
3193:
3191:
3189:
3187:
3179:
3175:
3171:
3167:
3166:
3158:
3156:
3154:
3152:
3144:
3140:
3136:
3132:
3128:
3124:
3120:
3113:
3111:
3103:
3099:
3095:
3091:
3088:(1): 93–109,
3087:
3083:
3082:
3077:
3071:
3069:
3067:
3065:
3063:
3061:
3053:
3047:
3043:
3036:
3034:
3032:
3027:
3016:
3013:
3010:
3007:
3004:
3001:
3000:
2994:
2992:
2988:
2984:
2983:planar graphs
2980:
2976:
2960:
2940:
2920:
2912:
2908:
2904:
2899:
2879:
2875:
2868:
2848:
2826:
2822:
2813:
2808:
2806:
2802:
2798:
2794:
2778:
2758:
2750:
2729:
2723:
2719:
2715:
2705:
2701:
2694:
2690:
2681:
2678:
2657:
2653:
2646:
2639:vertices and
2624:
2620:
2612:with at most
2611:
2606:
2588:
2584:
2563:
2543:
2535:
2530:
2528:
2524:
2520:
2504:
2484:
2470:
2466:
2451:
2448:
2443:
2439:
2418:
2414:
2408:
2405:
2400:
2396:
2389:
2385:
2379:
2355:
2332:
2329:
2306:
2298:
2297:random graphs
2294:
2289:
2274:
2251:
2245:
2225:
2217:
2201:
2181:
2173:
2168:
2154:
2146:
2130:
2122:
2106:
2086:
2083:
2080:
2075:
2067:
2064:
2061:
2053:
2049:
2045:
2025:
2005:
1997:
1993:
1977:
1974:
1971:
1951:
1928:
1925:
1922:
1916:
1913:
1910:
1907:
1904:
1898:
1895:
1892:
1869:
1849:
1829:
1806:
1801:
1797:
1784:
1767:
1763:
1757:
1753:
1741:
1737:
1718:
1714:
1708:
1704:
1680:
1677:
1674:
1651:
1647:
1641:
1633:
1630:
1627:
1597:
1593:
1587:
1583:
1559:
1536:
1532:
1526:
1522:
1498:
1478:
1458:
1438:
1424:
1422:
1418:
1414:
1410:
1405:
1390:
1387:
1384:
1362:
1359:
1356:
1336:
1327:
1323:
1307:
1301:
1281:
1275:
1255:
1235:
1232:
1229:
1221:
1217:
1213:
1209:
1204:
1201:
1197:
1193:
1188:
1186:
1182:
1178:
1173:
1170:
1166:
1161:
1156:
1154:
1150:
1146:
1141:
1136:
1131:
1117:
1109:
1105:
1089:
1069:
1054:
1040:
1037:
1017:
997:
977:
957:
937:
917:
897:
888:
874:
854:
834:
814:
794:
774:
754:
734:
714:
694:
691:
688:
668:
648:
604:
590:
588:
584:
580:
564:
544:
536:
533:
517:
509:
493:
480:
471:
469:
453:
409:
377:
349:
321:
282:
280:
276:
257:
253:
247:
243:
239:
236:
210:
203:vertices and
190:
181:
179:
175:
171:
167:
163:
159:
155:
151:
149:
143:
139:
135:
131:
126:
112:
104:
100:
96:
92:
76:
53:
50:
47:
41:
38:
30:
26:
22:
4735:
4701:
4697:
4691:
4670:(1): 57–75,
4667:
4663:
4657:
4633:
4627:
4621:
4589:
4583:
4547:
4529:
4487:
4483:
4477:
4451:
4445:
4432:
4406:
4400:
4364:
4360:
4347:
4321:
4315:
4306:
4267:(1): 67–83,
4264:
4258:
4223:
4217:
4207:
4173:
4167:
4125:
4119:
4112:Frieze, Alan
4106:
4074:
4068:
4040:
4027:
4010:
3992:
3986:
3954:
3950:
3937:
3911:
3872:
3866:
3860:
3836:
3832:
3826:
3794:
3790:
3784:
3750:
3744:
3718:
3712:
3691:
3665:
3659:
3654:Kou, L. T.;
3636:(2): 544–546
3633:
3629:
3623:
3615:
3609:
3567:
3561:
3508:
3502:
3493:
3452:
3406:
3400:
3339:
3333:
3308:
3304:
3266:
3260:
3217:
3213:
3169:
3163:
3126:
3122:
3085:
3079:
3041:
3015:Clique cover
2900:
2814:better than
2809:
2531:
2527:split graphs
2476:
2467:
2290:
2169:
1996:sparse graph
1785:
1742:has at most
1430:
1427:Upper bounds
1406:
1325:
1215:
1211:
1205:
1189:
1174:
1157:
1144:
1132:
1104:hyperspheres
1060:
1057:Applications
889:
596:
586:
582:
578:
485:
467:
293:
182:
177:
173:
169:
165:
161:
157:
153:
147:
146:
142:clique cover
138:clique cover
137:
133:
129:
127:
28:
25:graph theory
21:mathematical
18:
4704:: 187–208,
4312:Gyárfás, A.
4116:Reed, Bruce
4050:Erdős, Paul
3551:Pósa, Louis
3547:Erdős, Paul
3511:: 303–307,
3220:(2): 2–15,
3009:Bound graph
2975:linear time
2519:NP-complete
2216:line graphs
2038:is at most
1964:is at most
1185:fiber optic
1140:bitwise and
1110:is at most
593:Equivalence
285:Definitions
95:finite sets
31:of a graph
4749:Categories
4077:(1): 1–5,
4024:Katona, G.
4016:Lovász, L.
3705:Aronov, B.
3349:1608.07723
3250:Alon, Noga
3022:References
1992:complement
1862:, and let
1324:, and the
1192:statistics
1160:scheduling
1108:sphericity
176:, and the
101:needed to
4737:MathWorld
4544:Alavi, Y.
4522:203036455
4274:1203.1754
4135:1103.4870
4020:Erdős, P.
3819:122068627
3572:CiteSeerX
3485:247570676
3301:Orlin, J.
2989:based on
2801:treewidth
2603:distinct
2449:
2406:
2376:Θ
2084:
1908:≤
1896:−
1771:⌋
1750:⌊
1722:⌋
1701:⌊
1678:−
1655:⌋
1631:−
1622:⌊
1601:⌋
1580:⌊
1540:⌋
1519:⌊
1388:−
1360:−
1305:→
1279:→
1233:−
1208:food webs
1165:compilers
692:∈
535:subgraphs
23:field of
4614:33081703
4299:11264145
4099:26565829
4060:(1993),
4026:(eds.),
3910:(eds.),
3709:Suri, S.
3701:Alon, N.
3684:15059696
3553:(1966),
3451:(1979),
3395:(2007),
3374:67770018
3283:13522339
3252:(1986),
3234:15057639
3205:(2009),
3143:31868129
2997:See also
2099:, where
532:complete
150:-content
4710:1160076
4684:0731027
4650:1143909
4606:1723018
4556:0634549
4514:4050008
4470:1371491
4425:1835592
4381:6887887
4340:1078317
4291:3448348
4240:2112490
4200:0731572
4160:7326662
4152:1364022
4091:1221173
3979:6254096
3971:2054656
3889:0679638
3853:2418523
3811:2063995
3777:6498253
3737:1298916
3594:0186575
3527:0015448
3477:0519066
3425:2335890
3366:3904838
3102:0770871
2523:squares
2291:In the
2119:is the
1738:that a
508:cliques
318:be any
275:NP-hard
99:cliques
19:In the
4708:
4682:
4648:
4612:
4604:
4554:
4520:
4512:
4468:
4423:
4379:
4338:
4297:
4289:
4238:
4198:
4188:
4158:
4150:
4097:
4089:
3999:
3977:
3969:
3926:
3887:
3851:
3817:
3809:
3775:
3765:
3735:
3682:
3602:646660
3600:
3592:
3574:
3525:
3483:
3475:
3465:
3423:
3372:
3364:
3281:
3232:
3141:
3100:
3048:
2610:kernel
2145:degree
1822:. Let
1377:minus
374:is an
172:, the
164:, the
89:as an
27:, the
4610:S2CID
4518:S2CID
4377:S2CID
4357:(PDF)
4295:S2CID
4269:arXiv
4156:S2CID
4130:arXiv
4095:S2CID
4065:(PDF)
3975:S2CID
3947:(PDF)
3815:S2CID
3773:S2CID
3680:S2CID
3598:S2CID
3558:(PDF)
3370:S2CID
3344:arXiv
3279:S2CID
3257:(PDF)
3230:S2CID
3210:(PDF)
3139:S2CID
1994:of a
1106:(its
156:, or
103:cover
4186:ISBN
3997:ISBN
3924:ISBN
3763:ISBN
3481:OCLC
3463:ISBN
3046:ISBN
2123:and
1914:<
1294:and
1194:and
1167:for
1010:and
661:has
446:has
294:Let
4672:doi
4638:doi
4594:doi
4500:hdl
4492:doi
4488:270
4456:doi
4411:doi
4407:167
4369:doi
4326:doi
4279:doi
4228:doi
4178:doi
4140:doi
4079:doi
3959:doi
3916:doi
3877:doi
3841:doi
3799:doi
3755:doi
3723:doi
3670:doi
3582:doi
3513:doi
3411:doi
3354:doi
3313:doi
3271:doi
3222:doi
3174:doi
3170:154
3131:doi
3090:doi
2977:in
2751:in
2525:of
2517:is
2440:log
2397:log
2295:of
1214:or
1190:In
1130:).
950:of
581:or
537:of
510:in
350:of
231:min
132:or
93:of
4751::
4734:,
4730:,
4706:MR
4702:11
4700:,
4680:MR
4678:,
4668:13
4666:,
4646:MR
4644:,
4634:40
4632:,
4608:,
4602:MR
4600:,
4590:15
4588:,
4578:;
4567:^
4552:MR
4542:;
4516:,
4510:MR
4508:,
4498:,
4486:,
4466:MR
4464:,
4452:41
4450:,
4440:;
4421:MR
4419:,
4405:,
4388:^
4375:,
4363:,
4359:,
4336:MR
4334:,
4322:85
4320:,
4293:,
4287:MR
4285:,
4277:,
4265:45
4263:,
4247:^
4236:MR
4234:,
4224:18
4222:,
4196:MR
4194:,
4184:,
4154:,
4148:MR
4146:,
4138:,
4126:15
4124:,
4114:;
4093:,
4087:MR
4085:,
4075:13
4073:,
4067:,
4056:;
4052:;
4048:;
4022:;
3973:,
3967:MR
3965:,
3955:90
3953:,
3949:,
3922:,
3896:^
3885:MR
3883:,
3871:,
3849:MR
3847:,
3837:52
3835:,
3813:,
3807:MR
3805:,
3795:13
3793:,
3771:,
3761:,
3733:MR
3731:,
3719:12
3717:,
3707:;
3703:;
3699:;
3678:,
3666:21
3664:,
3646:^
3634:16
3632:,
3596:,
3590:MR
3588:,
3580:,
3568:18
3566:,
3560:,
3534:^
3523:MR
3521:,
3509:33
3479:,
3473:MR
3471:,
3461:,
3447:;
3432:^
3421:MR
3419:,
3405:,
3399:,
3381:^
3368:,
3362:MR
3360:,
3352:,
3340:90
3338:,
3324:^
3309:80
3307:,
3290:^
3277:,
3265:,
3259:,
3241:^
3228:,
3218:13
3216:,
3212:,
3185:^
3168:,
3150:^
3137:,
3127:22
3125:,
3121:,
3109:^
3098:MR
3096:,
3086:10
3084:,
3059:^
3030:^
2993:.
2747:,
2529:.
2167:.
2081:ln
887:.
589:.
470:.
281:.
180:.
168:,
152:,
125:.
4674::
4640::
4596::
4502::
4494::
4458::
4413::
4371::
4365:6
4328::
4281::
4271::
4230::
4180::
4142::
4132::
4081::
3961::
3918::
3879::
3873:3
3843::
3801::
3757::
3725::
3672::
3584::
3515::
3413::
3407:9
3356::
3346::
3315::
3273::
3267:6
3224::
3176::
3133::
3092::
2961:v
2941:v
2921:v
2885:)
2880:2
2876:n
2872:(
2869:O
2849:c
2827:c
2823:n
2779:k
2759:k
2733:)
2730:1
2727:(
2724:O
2720:n
2716:+
2711:)
2706:k
2702:4
2698:(
2695:O
2691:2
2663:)
2658:k
2654:4
2650:(
2647:O
2625:k
2621:2
2589:k
2585:2
2564:k
2544:n
2505:k
2485:G
2452:n
2444:2
2419:,
2415:)
2409:n
2401:2
2390:2
2386:n
2380:(
2356:n
2333:2
2330:1
2307:n
2275:G
2255:)
2252:G
2249:(
2246:L
2226:G
2202:n
2182:n
2155:G
2131:d
2107:e
2087:n
2076:2
2072:)
2068:1
2065:+
2062:d
2059:(
2054:2
2050:e
2046:2
2026:G
2006:n
1978:t
1975:+
1972:p
1952:G
1932:)
1929:1
1926:+
1923:t
1920:(
1917:t
1911:p
1905:t
1902:)
1899:1
1893:t
1890:(
1870:t
1850:G
1830:p
1807:4
1802:2
1798:n
1768:4
1764:/
1758:2
1754:n
1719:4
1715:/
1709:2
1705:n
1681:1
1675:n
1652:4
1648:/
1642:2
1638:)
1634:2
1628:n
1625:(
1598:4
1594:/
1588:2
1584:n
1560:n
1537:4
1533:/
1527:2
1523:n
1499:n
1479:m
1459:m
1439:m
1403:.
1391:2
1385:n
1363:2
1357:n
1337:n
1308:w
1302:v
1282:w
1276:u
1256:w
1236:v
1230:u
1118:k
1090:k
1070:k
1041:v
1038:u
1018:v
998:u
978:v
958:G
938:v
918:k
898:G
875:U
855:k
835:G
815:y
795:y
775:G
755:x
735:x
715:G
695:U
689:x
669:k
649:U
627:F
605:G
565:G
545:G
530:(
518:G
494:G
454:k
432:F
410:k
388:F
360:F
332:F
304:F
261:)
258:4
254:/
248:2
244:n
240:,
237:m
234:(
211:m
191:n
148:R
113:G
77:G
57:)
54:E
51:,
48:V
45:(
42:=
39:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
