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