322:
this characterization remains invariant under complementation of graphs, it implies the perfect graph theorem. One direction of this characterization follows easily from the original definition of perfect: the number of vertices in any graph equals the sum of the sizes of the color classes in an optimal coloring, and is less than or equal to the number of colors multiplied by the independence number. In a perfect graph, the number of colors equals the clique number, and can be replaced by the clique number in this inequality. The other direction can be proved directly, but it also follows from the strong perfect graph theorem: if a graph is not perfect, it contains an odd cycle or its complement, and in these subgraphs the product of the clique number and independence number is one less than the number of vertices.
902:
1860:
218:
2774:; for Berge graphs, this follows from the definition, while for perfect graphs it follows from the characterization using the product of the clique number and independence number. After the strong perfect graph theorem was proved, Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković discovered a polynomial time algorithm for testing the existence of odd holes or anti-holes. By the strong perfect graph theorem, this can be used to test whether a given graph is perfect, in polynomial time.
1982:
22:
479:
1675:
181:
756:
1508:
the graphs that are both comparability and incomparability graphs. A clique, in a permutation graph, is a subsequence of elements that appear in increasing order in the given permutation, and an independent set is a subsequence of elements that appear in decreasing order. In any perfect graph, the product of the clique number and independence number are at least the number of vertices; the special case of this inequality for permutation graphs is the
1382:
easier to prove directly than
Dilworth's theorem: if each element is labeled by the size of the largest chain in which it is maximal, then the subsets with equal labels form a partition into antichains, with the number of antichains equal to the size of the largest chain overall. Every bipartite graph is a comparability graph. Thus, Kőnig's theorem can be seen as a special case of Dilworth's theorem, connected through the theory of perfect graphs.
1386:
1516:
398:, and published by them in 2006. This work won its authors the 2009 Fulkerson Prize. The perfect graph theorem has a short proof, but the proof of the strong perfect graph theorem is long and technical, based on a deep structural decomposition of Berge graphs. Related decomposition techniques have also borne fruit in the study of other graph classes, and in particular for the
350:, in German, and the first use of the phrase "perfect graph" appears to be in a 1963 paper of Berge. In these works he unified Gallai's result with several similar results by defining perfect graphs, and he conjectured both the perfect graph theorem and the strong perfect graph theorem. In formulating these concepts, Berge was motivated by the concept of the
507:(as many disjoint edges as possible) together with one-vertex cliques for all remaining vertices, and its size is the number of vertices minus the number of matching edges. Therefore, this equality can be expressed equivalently as an equality between the size of the maximum matching and the minimum vertex cover in bipartite graphs, the usual formulation of
293:(the fewest number of cliques needed in a clique cover). More strongly, the same thing is true in every induced subgraph of the complement graph. This provides an alternative and equivalent definition of the perfect graphs: they are the graphs for which, in each induced subgraph, the independence number equals the clique cover number.
2645:, and for any graph the Lovász number is sandwiched between the chromatic number and clique number. Because these two numbers equal each other in perfect graphs, they also equal the Lovász number. Thus, they can be computed by approximating the Lovász number accurately enough and rounding the result to the nearest integer.
2656:. It leads to a polynomial time algorithm for computing the chromatic number and clique number in perfect graphs. However, solving these problems using the Lovász number and the ellipsoid method is complicated and has a high polynomial exponent. More efficient combinatorial algorithms are known for many special cases.
354:, by the fact that for (co-)perfect graphs it equals the independence number, and by the search for minimal examples of graphs for which this is not the case. Until the strong perfect graph theorem was proven, the graphs described by it (that is, the graphs with no odd hole and no odd antihole) were called
2769:
Beyond solving these problems, another important computational problem concerning perfect graphs is their recognition, the problem of testing whether a given graph is perfect. For many years the complexity of recognizing Berge graphs and perfect graphs were considered separately (as they were not yet
1381:
states that for every finite partial order, the size of the largest chain equals the minimum number of antichains into which the elements can be partitioned, or that every finite incomparability graph is perfect. These two theorems are equivalent via the perfect graph theorem, but Mirsky's theorem is
743:
of the underlying bipartite graph, the minimum number of colors needed to color the edges so that touching edges have different colors. Each color class forms a matching, and the chromatic index is the minimum number of matchings needed to cover all edges. The equality of maximum degree and chromatic
2659:
This method can also be generalized to find the maximum weight of a clique, in a weighted graph, instead of the clique number. A maximum or maximum weight clique itself, and an optimal coloring of the graph, can also be found by these methods, and a maximum independent set can be found by applying
2008:
have equal parity: either they are all even in length, or they are all odd in length. These include the distance-hereditary graphs, in which all induced paths between two vertices have the same length, and bipartite graphs, for which all paths (not just induced paths) between any two vertices have
1507:
in both the given sequence and its permutation. The complement of a permutation graph is another permutation graph, for the reverse of the given permutation. Therefore, as well as being incomparability graphs, permutation graphs are comparability graphs. In fact, the permutation graphs are exactly
1377:, in the theory of partial orders, states that for every finite partial order, the size of the largest antichain equals the minimum number of chains into which the elements can be partitioned. In the language of graphs, this can be stated as: every finite comparability graph is perfect. Similarly,
321:
These results can be combined in another characterization of perfect graphs: they are the graphs for which the product of the clique number and independence number is greater than or equal to the number of vertices, and for which the same is true for all induced subgraphs. Because the statement of
888:
The bipartite graphs, their complements, and the line graphs of bipartite graphs and their complements form four basic classes of perfect graphs that play a key role in the proof of the strong perfect graph theorem. According to the structural decomposition of perfect graphs used as part of this
209:
of a graph is the minimum number of colors in any coloring. The colorings shown are optimal, so the chromatic number is three for the 7-cycle and four for the other graph shown. The vertices of any clique must have different colors, so the chromatic number is always greater than or equal to the
304:
and their complements within a given graph. A cycle of odd length, greater than three, is not perfect: its clique number is two, but its chromatic number is three. By the perfect graph theorem, the complement of an odd cycle of length greater than three is also not perfect. The complement of a
1930:(connected to all other vertices). They are special cases of the split graphs and the trivially perfect graphs. They are exactly the graphs that are both trivially perfect and the complement of a trivially perfect graph; they are also exactly the graphs that are both cographs and split graphs.
1690:
is a graph that can be partitioned into a clique and an independent set. It can be colored by assigning a separate color to each vertex of a maximal clique, and then coloring each remaining vertex the same as a non-adjacent clique vertex. Therefore, these graphs have equal clique numbers and
1641:
whenever the two intervals have a point in common. Coloring these graphs can be used to model problems of assigning resources to tasks (such as classrooms to classes) with intervals describing the scheduled time of each task. Both interval graphs and permutation graphs are generalized by the
1950:, the graphs for which there exists an ordering that, when restricted to any induced subgraph, causes greedy coloring to be optimal. The cographs are exactly the graphs for which all vertex orderings have this property. Another subclass of perfectly orderable graphs are the complements of
1831:
are the graphs formed by a construction of this type in which, at the time a vertex is added, its neighbors form a clique. Chordal graphs may also be characterized as the graphs that have no holes (even or odd). They include as special cases the forests, the interval graphs, and the
1822:
Several families of perfect graphs can be characterized by an incremental construction in which the graphs in the family are built up by adding one vertex at a time, according to certain rules, which guarantee that after each vertex is added the graph remains perfect.
2414:, with a coefficient that is one in the columns of vertices that belong to the clique and zero in the remaining columns. The integral linear programs encoded by this matrix seek the maximum-weight independent set of the given graph, with weights given by the vector
724:. Therefore, in line graphs of bipartite graphs, the independence number and clique cover number are equal. Induced subgraphs of line graphs of bipartite graphs are line graphs of subgraphs, so the line graphs of bipartite graphs are perfect. Examples include the
491:(with at least one edge) the chromatic number and clique number both equal two. Their induced subgraphs remain bipartite, so bipartite graphs are perfect. Other important families of graphs are bipartite, and therefore also perfect, including for instance the
2009:
equal parity. Parity graphs are
Meyniel graphs, and therefore perfect: if a long odd cycle had only one chord, the two parts of the cycle between the endpoints of the chord would be induced paths of different parity. The prism over any parity graph (its
2798:
are defined as graphs in which, in every induced subgraph, the smallest dominating set (a set of vertices adjacent to all remaining vertices) equals the size of the smallest independent set that is a dominating set. These include, for instance, the
94:. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
365:
in 1972, who in the same year proved the stronger inequality between the number of vertices and the product of the clique number and independence number, without benefit of the strong perfect graph theorem. In 1991, Alfred Lehman won the
317:
that are not triangles are called "holes", and their complements are called "antiholes", so the strong perfect graph theorem can be stated more succinctly: a graph is perfect if and only if it has neither an odd hole nor an odd antihole.
1942:. Similarly, if the vertices of a distance-hereditary graph are colored in the order of an incremental construction sequence, the resulting coloring will be optimal. If the vertices of a comparability graph are colored in the order of a
210:
clique number. For some graphs, they are equal; for others, such as the ones shown, they are unequal. The perfect graphs are defined as the graphs for which these two numbers are equal, not just in the graph itself, but in every
889:
proof, every perfect graph that is not already in one of these four classes can be decomposed by partitioning its vertices into subsets, in one of four ways, called a 2-join, the complement of a 2-join, a homogeneous pair, or a
1441:), which form the vertices of the graph. The edges of a permutation graph connect pairs of elements whose ordering is reversed by the given permutation. These are naturally incomparability graphs, for a partial order in which
1289:
Finite comparability graphs (and their complementary incomparability graphs) are always perfect. A clique, in a comparability graph, comes from a subset of elements that are all pairwise comparable; such a subset is called a
1654:. These have been used to model human preferences under the assumption that, when items have utilities that are very close to each other, they will be incomparable. Intervals where every pair is nested or disjoint produce
1372:
is an antichain in the order and an independent set in the graph. Thus, a coloring of a comparability graph is a partition of its elements into antichains, and a clique cover is a partition of its elements into chains.
2409:
with this property is (up to removal of irrelevant "dominated" rows) the maximal clique versus vertex incidence matrix of a perfect graph. This matrix has a column for each vertex of the graph, and a row for each
1875:
are formed, starting from a single-vertex graph, by repeatedly adding degree-one vertices ("pendant vertices") or copies of existing vertices (with the same neighbors). Each vertex and its copy may be adjacent
482:
A bipartite graph (left) and its line graph (right). The shaded cliques in the line graph correspond to the vertices of the underlying bipartite graph, and have size equal to the degree of the corresponding
184:
A seven-vertex cycle and its complement, showing in each case an optimal coloring and a maximum clique (shown with heavy edges). Neither graph uses a number of colors equal to its clique size, so neither is
2793:
The equality of the clique number and chromatic number in perfect graphs has motivated the definition of other graph classes, in which other graph invariants are set equal to each other. For instance, the
1682:, obtained by giving each vertex of a maximal clique (heavy vertices and edges) a separate color, and then giving each remaining vertex the same color as a clique vertex to which it is not adjacent
2548:
corresponding to the maximal cliques in the graph. The perfect graphs are the only graphs for which the two polytopes defined in this way from independent sets and from maximal cliques coincide.
1907:. They have a restricted form of the distance-hereditary construction sequence, in which a false twin can only be added when its neighbors would form a clique. They include as special cases the
1699:, a disjoint union of cliques. These include also the bipartite graphs, for which the cluster graph is just a single clique. The unipolar graphs and their complements together form the class of
1750:
Other limiting properties of almost all perfect graphs can be determined by studying the generalized split graphs. In this way, it has been shown that almost all perfect graphs contain a
499:. By the perfect graph theorem, maximum independent sets in bipartite graphs have the same size as their minimum clique covers. The maximum independent set is complementary to a minimum
233:
of a perfect graph is itself perfect. The complement graph has an edge between two vertices if and only if the given graph does not. A clique, in the complement graph, corresponds to an
2580:, so that each two non-adjacent vertices have perpendicular labels, and so that all of the vectors lie in a cone with as small an opening angle as possible. Then, the Lovász number is
1978:, every vertex belongs to such an independent set. The Meyniel graphs can also be characterized as the graphs in which every odd cycle of length five or more has at least two chords.
2786:
if the chromatic number of the graphs in the class can be bounded by a function of their clique number. The perfect graphs are exactly the graphs for which this function is the
2619:
1884:). In every connected induced subgraph of these graphs, the distances between vertices are the same as in the whole graph. If only the twin operations are used, the result is a
346:, a much earlier result relating matchings and vertex covers in bipartite graphs. The first formulation of the concept of perfect graphs more generally was in a 1961 paper by
313:
for the perfect graphs: a graph is perfect if and only if its induced subgraphs include neither an odd cycle nor an odd anticycle of five or more vertices. In this context,
4142:
Skrien, Dale J. (1982). "A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs".
3192:
For the relation between the strong perfect graph theorem and the product characterization of perfect graphs, see remarks preceding
Theorem 2.1 and following Theorem 2.2.
1272:
1338:
735:
Because line graphs of bipartite graphs are perfect, their clique number equals their chromatic number. The clique number of the line graph of a bipartite graph is the
2530:
2138:
2083:
2639:
2501:
2204:
are given as two vectors. Although linear programs and integer programs are specified in this same way, they differ in that, in a linear program, the solution vector
2109:
1559:
1465:
1370:
1248:
1222:
1152:
1126:
1100:
1044:
1018:
988:
64:
382:. The conjectured strong perfect graph theorem became the focus of research in the theory of perfect graphs for many years, until its proof was announced in 2002 by
938:
879:
788:
841:
702:
613:
564:
2762:
The algorithm for finding an optimal coloring is more complicated, and depends on the duality theory of linear programs, using this clique-finding algorithm as a
1070:
2751:
2731:
2705:
2682:
2475:
2455:
2432:
2407:
2380:
2356:
2336:
2301:
2281:
2261:
2222:
2202:
2182:
2158:
2054:
1812:
1792:
1772:
1745:
1725:
1639:
1619:
1599:
1579:
1505:
1485:
1439:
1419:
1192:
1172:
962:
812:
722:
673:
653:
633:
584:
532:
279:
259:
2307:
if an optimal solution to the integer program is also optimal for the linear program. (Otherwise, the ratio between the two solution values is called the
5061:
Jansen, Klaus (1998). "A new characterization for parity graphs and a coloring problem with costs". In
Lucchesi, Claudio L.; Moura, Arnaldo V. (eds.).
4799:
Gavril, Fanica (1972). "Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph".
4475:
Graphs and
Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University, June 18–22, 1973
885:, sets of triangles sharing an edge. These components are perfect, and their combination preserves perfection, so every line perfect graph is perfect.
462:. Other important classes of graphs, defined by having a structure related to the holes and antiholes of the strong perfect graph theorem, include the
3207:
197:
is a subset of its vertices that are all adjacent to each other, such as the subsets of vertices connected by heavy edges in the illustration. The
1282:
of a partially ordered set has the set elements as its vertices, with an edge connecting any two comparable elements. Its complement is called an
2303:
are used to define both a linear program and an integer program, they commonly have different optimal solutions. The linear program is called an
402:. The symmetric characterization of perfect graphs in terms of the product of clique number and independence number was originally suggested by
1286:. Different partial orders may have the same comparability graph; for instance, reversing all comparisons changes the order but not the graph.
4512:
Proceedings of the Eighth
Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977)
2641:
is the half-angle of this cone. Despite this complicated definition, an accurate numerical value of the Lovász number can be computed using
1298:
by the given partial order. An independent set comes from a subset of elements no two of which are comparable; such a subset is called an
3482:
Surveys in combinatorics 2005. Papers from the 20th
British combinatorial conference, University of Durham, Durham, UK, July 10–15, 2005
2228:
as its coefficients, whereas in an integer program these unknown coefficients must be integers. This makes a very big difference in the
5118:
4973:
4587:
300:
gives a different way of defining perfect graphs, by their structure instead of by their properties. It is based on the existence of
4278:
201:
is the number of vertices in the largest clique: two in the illustrated seven-vertex cycle, and three in the other graph shown. A
1389:
The permutation graph of the permutation (4,3,5,1,2) connects pairs of elements whose ordering is reversed by the permutation.
1938:
algorithm, the result will be an optimal coloring. The reverse of the vertex ordering used in this construction is called an
205:
assigns a color to each vertex so that each two adjacent vertices have different colors, also shown in the illustration. The
414:
Many well-studied families of graphs are perfect, and in many cases the fact that these graphs are perfect corresponds to a
2660:
the same approach to the complement of the graph. For instance, a maximum clique can be found by the following algorithm:
508:
427:
343:
138:
418:
for some kinds of combinatorial structure defined by these graphs. Examples of this phenomenon include the perfection of
1946:
of its underlying partial order, the resulting coloring will be optimal. This property is generalized in the family of
5483:
5313:
5280:
5063:
LATIN '98: Theoretical
Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings
4947:
4490:
3826:
3752:
3489:
371:
739:
of any vertex of the underlying bipartite graph. The chromatic number of the line graph of a bipartite graph is the
305:
length-5 cycle is another length-5 cycle, but for larger odd lengths the complement is not a cycle; it is called an
2034:
310:
165:
4685:
4538:
3948:
3095:
2565:
2013:
with a single edge) is another parity graph, and the parity graphs are the only graphs whose prisms are perfect.
110:
5391:. Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985).
5016:
Cicerone, Serafino; Di
Stefano, Gabriele (1999). "Graph classes between parity and distance-hereditary graphs".
2304:
1814:
is not a generalized split graph, is unipolar or co-unipolar but not both, or is both unipolar and co-unipolar.
5427:
4192:
3632:
3327:
3005:
2908:
2831:
2576:
of these graphs. The Lovász number of any graph can be determined by labeling its vertices by high dimensional
387:
241:, a partition of the vertices of the given graph into cliques. The fact that the complement of a perfect graph
234:
1889:
375:
1934:
If the vertices of a chordal graph are colored in the order of an incremental construction sequence using a
1509:
146:
5337:
5018:
4834:
4629:
4065:
3886:
3470:
3300:; note that Chudnovsky et al define capacity using the complement of the graphs used for the definition in
3013:
3009:
2839:
2835:
395:
391:
297:
161:
79:
1855:-vertex clique and repeatedly adding a vertex so that it and its neighbors form a clique of the same size.
3301:
2010:
351:
66:) is perfect. Here it is colored with three colors, with one of its 3-vertex maximum cliques highlighted.
2583:
4864:
4801:
1990:
1947:
1872:
1864:
1833:
169:
4113:
Proof
Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968)
1966:
are graphs in which, in every induced subgraph, there exists an independent set that intersects all
4010:
3576:
3174:
2795:
2642:
2229:
1893:
729:
149:
on monotonic sequences, can be expressed in terms of the perfection of certain associated graphs.
5516:
5260:
4923:
4896:
4187:
4144:
4056:
2312:
1904:
1655:
1646:. Systems of intervals in which no two are nested produce a more restricted class of graphs, the
286:
142:
97:
The perfect graphs include many important families of graphs and serve to unify results relating
1257:
5341:
5333:
5187:. North-Holland Mathematics Studies. Vol. 88. North-Holland, Amsterdam. pp. 325–356.
4001:
2954:
2561:
2557:
1963:
1794:
occurs as an induced subgraph of a large random perfect graph is 0, 1/2, or 1, respectively as
1305:
991:
106:
102:
5381:
3400:
Mackenzie, Dana (July 5, 2002). "Mathematics: Graph theory uncovers the roots of perfection".
2710:
Use semidefinite programming to determine the clique number of the resulting induced subgraph.
2506:
2114:
2062:
1836:. The split graphs are exactly the graphs that are chordal and have a chordal complement. The
4507:
3684:
3022:
2624:
2480:
2088:
1892:
and can also be formed by a different construction process combining complementation and the
1538:
1444:
1374:
1343:
1227:
1201:
1131:
1105:
1079:
1023:
997:
967:
917:
848:
736:
459:
443:
226:
190:
153:
134:
126:
36:
5489:
5301:
5221:
5172:
3474:
3090:
2903:
362:
5450:
5404:
5385:
5237:
5200:
5139:
5088:
5039:
4994:
4957:
4753:
4708:
4650:
4559:
4519:
4444:
4420:
4360:
4299:
4258:
4213:
4165:
4120:
4086:
4033:
3971:
3909:
3855:
3796:
3762:
3713:
3653:
3597:
3499:
3350:
3228:
3116:
3053:
3017:
2976:
2929:
2870:
2161:
1291:
923:
857:
766:
451:
5245:
5147:
5096:
5079:
5047:
5002:
4761:
4716:
4658:
4610:
4567:
4376:
4315:
4221:
4173:
4128:
4094:
4041:
3979:
3917:
3863:
3804:
3770:
3705:
3661:
3613:
3507:
3358:
3244:
3124:
3069:
2984:
2937:
2886:
817:
678:
589:
540:
117:, despite their greater complexity for non-perfect graphs. In addition, several important
8:
5473:
5225:
5176:
5113:
2386:
2026:
1378:
1279:
1073:
1049:
910:
882:
749:
492:
447:
439:
290:
282:
130:
5467:
5217:
5168:
3372:
901:
5363:
4934:. Cambridge Studies in Advanced Mathematics. Vol. 89. Cambridge University Press.
4470:
4448:
4364:
4338:
4303:
3843:
3717:
3601:
3427:
3232:
3057:
3031:
2962:
2874:
2736:
2716:
2690:
2667:
2653:
2648:
The solution method for semidefinite programs, used by this algorithm, is based on the
2460:
2440:
2417:
2392:
2365:
2341:
2321:
2286:
2266:
2246:
2207:
2187:
2167:
2143:
2057:
2039:
2022:
1797:
1777:
1757:
1730:
1710:
1707:
perfect graphs are generalized split graphs, in the sense that the fraction of perfect
1647:
1624:
1604:
1584:
1564:
1490:
1470:
1424:
1404:
1177:
1157:
947:
941:
844:
797:
760:
707:
658:
638:
618:
569:
517:
264:
244:
5441:
5422:
5192:
5031:
2338:(that is, matrices where all coefficients are 0 or 1) with the following property: if
5309:
5276:
5131:
4986:
4943:
4848:
4829:
4642:
4601:
4582:
4551:
4486:
4452:
4406:
4205:
4078:
3997:
3748:
3721:
3485:
3431:
3419:
3402:
3261:(1961). "Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind".
3236:
3108:
3061:
2959:
Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002)
2921:
2787:
2763:
2533:
1751:
1659:
1394:
4514:. Congressus Numerantium. Vol. XIX. Winnipeg: Utilitas Math. pp. 311–315.
4393:
Rose, Donald J. (December 1970). "Triangulated graphs and the elimination process".
4368:
4307:
3605:
5436:
5367:
5355:
5329:
5268:
5241:
5188:
5143:
5127:
5092:
5074:
5066:
5043:
5027:
4998:
4982:
4935:
4905:
4876:
4843:
4810:
4775:
4757:
4712:
4694:
4654:
4638:
4606:
4596:
4563:
4547:
4478:
4432:
4402:
4372:
4348:
4311:
4287:
4246:
4217:
4201:
4169:
4153:
4124:
4090:
4074:
4037:
4019:
3975:
3957:
3913:
3895:
3859:
3835:
3800:
3766:
3740:
3701:
3693:
3675:
3657:
3641:
3609:
3585:
3545:
3503:
3466:
3411:
3354:
3336:
3240:
3216:
3183:
3154:
3120:
3104:
3065:
3041:
3001:
2980:
2933:
2917:
2882:
2878:
2858:
2827:
2649:
2545:
2541:
1943:
1927:
1859:
745:
504:
431:
383:
335:
230:
211:
206:
194:
157:
91:
3521:
2573:
732:. Every line graph of a bipartite graph is an induced subgraph of a rook's graph.
403:
5501:
5446:
5400:
5233:
5196:
5135:
5084:
5065:. Lecture Notes in Computer Science. Vol. 1380. Springer. pp. 249–260.
5035:
4990:
4953:
4894:
Gyárfás, A.; Lehel, J. (June 1988). "On-line and first fit colorings of graphs".
4749:
4734:
4730:
4704:
4646:
4555:
4536:
Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986). "Distance-hereditary graphs".
4515:
4440:
4356:
4295:
4273:
4254:
4209:
4161:
4116:
4108:
4082:
4029:
3967:
3905:
3851:
3792:
3758:
3709:
3649:
3630:; Gurvich, V. (2006). "Perfect graphs, kernels, and cores of cooperative games".
3593:
3495:
3346:
3224:
3112:
3049:
2972:
2925:
2866:
2843:
2800:
2569:
2359:
2308:
2233:
1994:
1951:
1935:
1923:
1919:
1900:
1643:
740:
725:
503:, a set of vertices that touches all edges. A minimum clique cover consists of a
488:
419:
415:
399:
367:
339:
118:
114:
3415:
635:
that share an endpoint. Line graphs have two kinds of cliques: sets of edges in
4735:"Linear-time certifying recognition algorithms and forbidden induced subgraphs"
4676:
3935:
3645:
3341:
3322:
3045:
2411:
2316:
2030:
1967:
1908:
1663:
1532:
1528:
1520:
1275:
890:
852:
379:
217:
202:
98:
87:
83:
5359:
4291:
3900:
3881:
3739:. Advances in Mathematics. Vol. 7. New York: Springer. pp. 353–368.
2862:
2770:
known to be equivalent) and both remained open. They were both known to be in
5510:
5418:
5346:
4939:
4624:
4237:
3877:
3744:
3445:
3145:
3143:
Gasparian, G. S. (June 1996). "Minimal imperfect graphs: A simple approach".
2713:
If this clique number is the same as for the whole graph, permanently remove
1971:
1828:
1727:-vertex graphs that are generalized split graphs goes to one in the limit as
1696:
1401:
on a totally ordered sequence of elements (conventionally, the integers from
906:
467:
463:
314:
198:
122:
5272:
4627:; Lerchs, H.; Stewart Burlingham, L. (1981). "Complement reducible graphs".
4909:
4880:
4699:
4680:
4466:
4157:
3993:
3962:
3944:"Transitive orientation of graphs and identification of permutation graphs"
3943:
3784:
3423:
3280:
3258:
3202:
2005:
2001:
1986:
500:
496:
435:
347:
331:
238:
71:
26:
5479:
5304:(1983). "Perfect graphs". In Beineke, Lowell W.; Wilson, Robin J. (eds.).
3680:"Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre"
2783:
1302:. For instance, in the illustrated partial order and comparability graph,
5497:
3939:
3931:
3821:
3627:
2577:
2537:
2315:
for the integer program.) Perfect graphs may be used to characterize the
2225:
1981:
1912:
1687:
1679:
1398:
1295:
301:
21:
101:
and cliques in those families. For instance, in all perfect graphs, the
5070:
4482:
4477:. Lecture Notes in Mathematics. Vol. 406. Springer. pp. 1–9.
4436:
4250:
4060:
3847:
3697:
3589:
3220:
3187:
3158:
1704:
535:
478:
423:
30:
4352:
4235:
Hammer, Peter L.; Simeone, Bruno (1981). "The splittance of a graph".
4024:
4005:
1674:
180:
4927:
3036:
2967:
1844:
1651:
1299:
755:
455:
378:, for his work on generalizations of the theory of perfect graphs to
342:
is perfect; this result can also be viewed as a simple equivalent of
5250:
See especially chapter 9, "Stable Sets in Graphs", pp. 273–303.
4814:
3839:
3679:
1899:
The graphs that are both chordal and distance-hereditary are called
1385:
675:. In bipartite graphs, there are no triangles, so a clique cover in
4425:
Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
4343:
3304:, and include a logarithm that the linked article does not include.
1691:
chromatic numbers, and are perfect. A broader class of graphs, the
309:. The strong perfect graph theorem asserts that these are the only
3172:
Padberg, Manfred W. (December 1974). "Perfect zero-one matrices".
2758:
Return the subgraph that remains after all the permanent removals.
237:
in the given. A coloring of the complement graph corresponds to a
4583:"On a class of posets and the corresponding comparability graphs"
4329:
McDiarmid, Colin; Yolov, Nikola (2019). "Random perfect graphs".
3992:
3882:"Remarks on Dilworth's theorem in relation to transversal theory"
2237:
1885:
1515:
4867:(September 1989). "Some classes of perfectly orderable graphs".
3297:
3263:
Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe
3000:
2826:
2004:
is defined by the property that between every two vertices, all
4623:
2906:(1972). "Normal hypergraphs and the perfect graph conjecture".
2790:, both for the graph itself and for all its induced subgraphs.
2016:
1837:
1535:, orderings defined by sets of intervals on the real line with
334:
that in modern language can be interpreted as stating that the
5328:
5180:
1922:
are formed from an empty graph by repeatedly adding either an
748:. In arbitrary simple graphs, they can differ by one; this is
2782:
Generalizing the perfect graphs, a graph class is said to be
2771:
2029:. Both linear programs and integer programs are expressed in
1601:. In the corresponding interval graph, there is an edge from
920:
is defined by its set of elements, and a comparison relation
330:
The theory of perfect graphs developed from a 1958 result of
3373:"The 1991 D. R. Fulkerson Prizes in Discrete Mathematics"
1911:
consisting of cliques joined at a single vertex, and the
1669:
1340:
is a chain in the order and a clique in the graph, while
5259:
5216:
5167:
4780:
Information System on Graph Classes and their Inclusions
3526:
Information System on Graph Classes and their Inclusions
3287:. Calcutta: Indian Statistical Institute. pp. 1–21.
2664:
Loop through the vertices of the graph. For each vertex
1662:. In them, the independence number equals the number of
5116:(1975). "On certain polytopes associated with graphs".
2232:
of these problems: linear programming can be solved in
5417:
3824:(1971). "A dual of Dilworth's decomposition theorem".
2457:
defined in this way from a perfect graph, the vectors
2021:
Perfect graphs are closely connected to the theory of
2961:. Beijing: Higher Education Press. pp. 547–559.
2739:
2719:
2693:
2670:
2627:
2586:
2509:
2483:
2463:
2443:
2420:
2395:
2368:
2344:
2324:
2289:
2269:
2249:
2210:
2190:
2170:
2146:
2117:
2091:
2065:
2042:
1800:
1780:
1774:
is an arbitrary graph, the limiting probability that
1760:
1733:
1713:
1627:
1607:
1587:
1567:
1541:
1493:
1473:
1447:
1427:
1407:
1346:
1308:
1260:
1230:
1204:
1180:
1160:
1134:
1108:
1082:
1052:
1026:
1000:
970:
950:
926:
860:
820:
800:
769:
710:
681:
661:
641:
621:
592:
572:
543:
520:
267:
247:
164:
characterizes the perfect graphs in terms of certain
39:
5386:"Problems from the world surrounding perfect graphs"
3438:
3380:
Optima: Mathematical Optimization Society Newsletter
3365:
763:, with black bipartite biconnected components, blue
175:
5230:
Geometric Algorithms and Combinatorial Optimization
4971:Hoàng, C. T. (1987). "On a conjecture of Meyniel".
4054:
473:
5015:
3574:Trotter, L. E. Jr. (1977). "Line perfect graphs".
2745:
2725:
2699:
2676:
2633:
2613:
2572:. The algorithm for the general case involves the
2524:
2495:
2469:
2449:
2426:
2401:
2374:
2350:
2330:
2295:
2275:
2255:
2216:
2196:
2176:
2152:
2132:
2103:
2077:
2048:
1806:
1786:
1766:
1739:
1719:
1633:
1613:
1593:
1573:
1553:
1499:
1479:
1459:
1433:
1413:
1364:
1332:
1266:
1242:
1216:
1186:
1166:
1146:
1120:
1094:
1064:
1038:
1012:
982:
956:
932:
873:
835:
806:
782:
744:index, in bipartite graphs, is another theorem of
716:
696:
667:
647:
627:
607:
578:
558:
526:
273:
253:
58:
4395:Journal of Mathematical Analysis and Applications
3735:Harzheim, Egbert (2005). "Comparability graphs".
3465:
3208:Acta Mathematica Academiae Scientiarum Hungaricae
2949:
2947:
534:, is the same thing as an independent set in the
5508:
4729:
4681:"A characterization of certain ptolemaic graphs"
3930:
3484:. Cambridge University Press. pp. 153–171.
3316:
3314:
3312:
3310:
3093:(1972). "A characterization of perfect graphs".
1915:in which each biconnected component is a clique.
5108:
5106:
4276:(1992). "Almost all Berge graphs are perfect".
4063:(1988). "Trapezoid graphs and their coloring".
3569:
3567:
3565:
3563:
2957:(2002). "The strong perfect graph conjecture".
1888:. The cographs are the comparability graphs of
1847:, are chordal graphs formed by starting with a
5300:
4328:
4115:. New York: Academic Press. pp. 139–146.
3816:
3814:
3393:
3205:(1958). "Maximum-minimum Sätze über Graphen".
3085:
3083:
3081:
3079:
2944:
2898:
2896:
5421:; Flandrin, Evelyne; Ryjáček, Zdeněk (1997).
5253:
4922:
4827:
4535:
4234:
4180:
3728:
3307:
3257:
566:, a graph that has a vertex for each edge in
5498:Information System on Graph Class Inclusions
5374:
5103:
4893:
4828:Hammer, Peter L.; Maffray, Frédéric (1990).
4674:
4505:
4271:
4101:
3870:
3791:. London: Academic Press. pp. 155–165.
3626:
3560:
2017:Matrices, polyhedra, and integer programming
1817:
1359:
1347:
1327:
1309:
5294:
5265:Algorithmic Graph Theory and Perfect Graphs
5212:
5210:
5163:
5161:
5159:
5157:
5054:
4792:
4135:
3811:
3138:
3136:
3134:
3076:
2996:
2994:
2893:
2822:
2820:
2818:
2816:
438:in bipartite graphs, and the perfection of
214:obtained by deleting some of its vertices.
5322:
5181:"Polynomial algorithms for perfect graphs"
4964:
4670:
4668:
4531:
4529:
4228:
3787:(1967). "Some classes of perfect graphs".
3777:
3668:
3538:
3273:
3195:
2953:
2382:the resulting linear program is integral.
5440:
5119:Journal of Combinatorial Theory, Series B
5078:
4974:Journal of Combinatorial Theory, Series B
4862:
4847:
4768:
4698:
4617:
4600:
4588:Journal of Combinatorial Theory, Series B
4574:
4459:
4342:
4023:
3986:
3961:
3899:
3514:
3399:
3340:
3251:
3142:
3035:
2966:
655:with a common endpoint, and triangles in
16:Graph with tight clique-coloring relation
5411:
5207:
5154:
4279:Combinatorics, Probability and Computing
4186:
4048:
3924:
3734:
3320:
3131:
2991:
2813:
1980:
1858:
1673:
1514:
1384:
1254:otherwise. For instance, set inclusion (
900:
754:
477:
361:The perfect graph theorem was proven by
216:
179:
172:for testing whether a graph is perfect.
160:of a perfect graph is also perfect. The
90:, both in the graph itself and in every
20:
5380:
5306:Selected Topics in Graph Theory, Vol. 2
5112:
5009:
4916:
4723:
4665:
4526:
4388:
4386:
4322:
4265:
4107:
3876:
3620:
3573:
3459:
3171:
2544:of independent sets in the graph, with
1954:, a generalization of interval graphs.
1695:can be partitioned into a clique and a
896:
5509:
5060:
4798:
4469:(1974). "Recent results on trees". In
4465:
4141:
3820:
3201:
3165:
2477:satisfying the system of inequalities
1670:Split graphs and random perfect graphs
1581:is completely to the left of interval
4970:
4419:
4413:
3783:
3674:
3544:
3279:
409:
5344:(2005). "Recognizing Berge graphs".
5183:. In Berge, C.; Chvátal, V. (eds.).
4887:
4856:
4821:
4580:
4499:
4392:
4383:
4190:(1978). "Trivially perfect graphs".
3789:Graph Theory and Theoretical Physics
2085:, subject to the linear constraints
1957:
1863:Three types of vertex addition in a
909:of a partially ordered set, and its
586:and an edge between two vertices in
4423:(1961). "On rigid circuit graphs".
3475:"The structure of claw-free graphs"
3448:. Mathematical Optimization Society
2777:
13:
5308:. Academic Press. pp. 55–87.
4331:Random Structures & Algorithms
3018:"The strong perfect graph theorem"
2614:{\displaystyle 1/\cos ^{2}\theta }
1531:are the incomparability graphs of
14:
5528:
5484:American Institute of Mathematics
5461:
3827:The American Mathematical Monthly
1926:(connected to nothing else) or a
704:corresponds to a vertex cover in
372:Mathematical Optimization Society
261:is also perfect implies that, in
176:Definitions and characterizations
5469:The Strong Perfect Graph Theorem
4004:; Spieksma, Frits C. R. (2007).
2311:, and is important in analyzing
1650:, the incomparability graphs of
474:Bipartite graphs and line graphs
221:Two complementary perfect graphs
5494:, maintained by Václav Chvátal.
5480:Open problems on perfect graphs
4686:Canadian Journal of Mathematics
4539:Journal of Combinatorial Theory
4111:(1969). "Indifference graphs".
4006:"Interval scheduling: a survey"
3949:Canadian Journal of Mathematics
3446:"2009 Fulkerson Prize Citation"
3291:
3096:Journal of Combinatorial Theory
2684:, perform the following steps:
2566:maximum independent set problem
1903:, because their distances obey
1843:, central to the definition of
111:maximum independent set problem
5289:Annals of Discrete Mathematics
5080:11858/00-001M-0000-0014-7BE2-3
3548:(1931). "Gráfok és mátrixok".
1890:series-parallel partial orders
1658:, the comparability graphs of
830:
824:
691:
685:
602:
596:
553:
547:
1:
5442:10.1016/S0012-365X(96)00045-3
5423:"Claw-free graphs — A survey"
5193:10.1016/S0304-0208(08)72943-8
5032:10.1016/S0166-218X(99)00075-X
4830:"Completely separable graphs"
2806:
2551:
2236:, but integer programming is
2224:is allowed to have arbitrary
1523:and the intervals defining it
847:. These are the graphs whose
376:American Mathematical Society
5132:10.1016/0095-8956(75)90041-6
5019:Discrete Applied Mathematics
4987:10.1016/0095-8956(87)90047-5
4849:10.1016/0166-218x(90)90131-u
4835:Discrete Applied Mathematics
4643:10.1016/0166-218X(81)90013-5
4630:Discrete Applied Mathematics
4602:10.1016/0095-8956(78)90013-8
4552:10.1016/0095-8956(86)90043-2
4407:10.1016/0022-247x(70)90282-9
4206:10.1016/0012-365X(78)90178-4
4079:10.1016/0166-218X(88)90032-7
4066:Discrete Applied Mathematics
3887:Glasgow Mathematical Journal
3550:Matematikai és Fizikai Lapok
3109:10.1016/0095-8956(72)90045-7
2922:10.1016/0012-365X(72)90006-4
2844:"Progress on perfect graphs"
1976:very strongly perfect graphs
298:strong perfect graph theorem
162:strong perfect graph theorem
7:
4742:Nordic Journal of Computing
3416:10.1126/science.297.5578.38
3323:"Classes of perfect graphs"
3302:Shannon capacity of a graph
2556:In all perfect graphs, the
2243:When the same given values
851:are bipartite graphs, the
370:, sponsored jointly by the
352:Shannon capacity of a graph
311:forbidden induced subgraphs
166:forbidden induced subgraphs
10:
5533:
4733:; Kratsch, Dieter (2007).
4002:Papadimitriou, Christos H.
3646:10.1016/j.disc.2005.12.031
3342:10.1016/j.disc.2006.05.021
3285:Six Papers on Graph Theory
3283:(1963). "Perfect graphs".
3046:10.4007/annals.2006.164.51
2362:, then for all choices of
1948:perfectly orderable graphs
1873:distance-hereditary graphs
1834:maximal outerplanar graphs
1267:{\displaystyle \subseteq }
790:, and red triangular books
615:for each pair of edges in
325:
5360:10.1007/s00493-005-0012-8
4802:SIAM Journal on Computing
4292:10.1017/S0963548300000079
3901:10.1017/S0017089500003931
3378:. 1991 Prize Recipients.
3321:Hougardy, Stefan (2006).
2863:10.1007/s10107-003-0449-8
2796:domination perfect graphs
1865:distance-hereditary graph
1818:Incremental constructions
1747:grows arbitrarily large.
1333:{\displaystyle \{A,B,C\}}
730:complete bipartite graphs
514:A matching, in any graph
170:polynomial time algorithm
5261:Golumbic, Martin Charles
5185:Topics on perfect graphs
4940:10.1017/CBO9780511542985
4924:Golumbic, Martin Charles
4510:(1977). "Split graphs".
4473:; Harary, Frank (eds.).
4188:Golumbic, Martin Charles
4057:Golumbic, Martin Charles
4011:Naval Research Logistics
3745:10.1007/0-387-24222-8_12
3577:Mathematical Programming
3382:(35): 4–8. November 1991
3298:Chudnovsky et al. (2003)
3175:Mathematical Programming
2851:Mathematical Programming
2643:semidefinite programming
2525:{\displaystyle Ax\leq 1}
2313:approximation algorithms
2230:computational complexity
2133:{\displaystyle Ax\leq b}
2078:{\displaystyle c\cdot x}
2056:that maximizes a linear
1894:disjoint union of graphs
1701:generalized split graphs
1656:trivially perfect graphs
814:of a perfect line graph
470:, and their subclasses.
5399:(3–4): 413–441 (1988).
5393:Zastosowania Matematyki
5273:10.1016/C2013-0-10739-8
4897:Journal of Graph Theory
4869:Journal of Graph Theory
4145:Journal of Graph Theory
2634:{\displaystyle \theta }
2496:{\displaystyle x\geq 0}
2305:integral linear program
2104:{\displaystyle x\geq 0}
1964:strongly perfect graphs
1554:{\displaystyle x\leq y}
1460:{\displaystyle x\leq y}
1365:{\displaystyle \{C,D\}}
1274:) partially orders any
1243:{\displaystyle y\leq x}
1217:{\displaystyle x\leq y}
1147:{\displaystyle x\leq z}
1121:{\displaystyle y\leq z}
1095:{\displaystyle x\leq y}
1039:{\displaystyle y\leq x}
1013:{\displaystyle x\leq y}
983:{\displaystyle x\leq x}
287:maximum independent set
86:equals the size of the
59:{\displaystyle K_{3,3}}
4910:10.1002/jgt.3190120212
4881:10.1002/jgt.3190130407
4748:(1–2): 87–108 (2008).
4700:10.4153/CJM-1965-034-0
4508:Hammer, Peter Ladislaw
4158:10.1002/jgt.3190060307
3963:10.4153/CJM-1971-016-5
2747:
2727:
2701:
2678:
2635:
2615:
2562:maximum clique problem
2558:graph coloring problem
2526:
2497:
2471:
2451:
2428:
2403:
2376:
2352:
2332:
2297:
2277:
2257:
2218:
2198:
2178:
2154:
2134:
2105:
2079:
2050:
1997:
1867:
1808:
1788:
1768:
1741:
1721:
1683:
1678:Optimal coloring of a
1635:
1615:
1595:
1575:
1555:
1524:
1510:Erdős–Szekeres theorem
1501:
1481:
1461:
1435:
1415:
1390:
1366:
1334:
1268:
1244:
1218:
1188:
1168:
1148:
1122:
1096:
1066:
1040:
1014:
984:
958:
934:
913:
875:
849:biconnected components
837:
808:
791:
784:
718:
698:
669:
649:
629:
609:
580:
560:
528:
484:
460:partially ordered sets
406:and proven by Lovász.
275:
255:
222:
186:
147:Erdős–Szekeres theorem
135:partially ordered sets
107:maximum clique problem
103:graph coloring problem
67:
60:
4272:Prömel, Hans Jürgen;
3685:Mathematische Annalen
3023:Annals of Mathematics
2748:
2733:; otherwise, restore
2728:
2702:
2679:
2636:
2616:
2568:can all be solved in
2527:
2498:
2472:
2452:
2429:
2404:
2389:proved, every matrix
2377:
2353:
2333:
2298:
2278:
2258:
2219:
2199:
2179:
2155:
2135:
2106:
2080:
2051:
1984:
1862:
1809:
1789:
1769:
1742:
1722:
1677:
1636:
1616:
1596:
1576:
1556:
1518:
1502:
1482:
1462:
1436:
1416:
1388:
1367:
1335:
1284:incomparability graph
1269:
1245:
1219:
1189:
1169:
1149:
1123:
1097:
1067:
1041:
1015:
985:
959:
935:
933:{\displaystyle \leq }
918:partially ordered set
904:
876:
874:{\displaystyle K_{4}}
838:
809:
794:The underlying graph
785:
783:{\displaystyle K_{4}}
758:
728:, the line graphs of
719:
699:
670:
650:
630:
610:
581:
561:
529:
481:
276:
256:
227:perfect graph theorem
220:
183:
154:perfect graph theorem
113:can all be solved in
61:
24:
5482:, maintained by the
5428:Discrete Mathematics
5226:Schrijver, Alexander
5177:Schrijver, Alexander
4581:Jung, H. A. (1978).
4193:Discrete Mathematics
3640:(19–20): 2336–2354.
3633:Discrete Mathematics
3335:(19–20): 2529–2571.
3328:Discrete Mathematics
2909:Discrete Mathematics
2737:
2717:
2691:
2668:
2625:
2584:
2507:
2481:
2461:
2441:
2418:
2393:
2366:
2342:
2322:
2287:
2267:
2247:
2208:
2188:
2168:
2144:
2115:
2089:
2063:
2040:
1905:Ptolemy's inequality
1798:
1778:
1758:
1731:
1711:
1625:
1605:
1585:
1565:
1539:
1491:
1471:
1445:
1425:
1405:
1344:
1306:
1258:
1228:
1202:
1178:
1158:
1132:
1106:
1080:
1050:
1024:
998:
968:
948:
924:
897:Comparability graphs
858:
836:{\displaystyle L(G)}
818:
798:
767:
708:
697:{\displaystyle L(G)}
679:
659:
639:
619:
608:{\displaystyle L(G)}
590:
570:
559:{\displaystyle L(G)}
541:
518:
440:comparability graphs
265:
245:
37:
5291:57, Elsevier, 2004.
5232:. Springer-Verlag.
3994:Kolen, Antoon W. J.
2857:(1-2(B)): 405–422.
2687:Tentatively remove
2027:integer programming
1991:distance-hereditary
1880:) or non-adjacent (
1648:indifference graphs
1280:comparability graph
1065:{\displaystyle x=y}
911:comparability graph
291:clique cover number
283:independence number
5342:Vušković, Kristina
5334:Cornuéjols, Gérard
5267:. Academic Press.
5071:10.1007/BFb0054326
4776:"Threshold graphs"
4506:Földes, Stéphane;
4483:10.1007/bfb0066429
4437:10.1007/BF02992776
4251:10.1007/BF02579333
3998:Lenstra, Jan Karel
3698:10.1007/BF01456961
3590:10.1007/BF01593791
3522:"Bipartite graphs"
3221:10.1007/BF02020271
3188:10.1007/bf01580235
3159:10.1007/bf01844846
2955:Cornuéjols, Gérard
2743:
2723:
2697:
2674:
2654:linear programming
2631:
2611:
2522:
2493:
2467:
2447:
2424:
2399:
2372:
2348:
2328:
2293:
2273:
2253:
2214:
2194:
2174:
2150:
2130:
2101:
2075:
2058:objective function
2046:
2023:linear programming
1998:
1868:
1804:
1784:
1764:
1737:
1717:
1684:
1631:
1611:
1591:
1571:
1561:whenever interval
1551:
1525:
1497:
1477:
1457:
1431:
1411:
1397:is defined from a
1391:
1375:Dilworth's theorem
1362:
1330:
1264:
1240:
1214:
1184:
1164:
1144:
1118:
1092:
1062:
1036:
1010:
980:
954:
944:(for all elements
930:
914:
871:
845:line perfect graph
833:
804:
792:
780:
761:line perfect graph
714:
694:
665:
645:
625:
605:
576:
556:
524:
485:
444:Dilworth's theorem
442:, associated with
426:, associated with
410:Families of graphs
271:
251:
223:
187:
127:Dilworth's theorem
68:
56:
5330:Chudnovsky, Maria
5218:Grötschel, Martin
5169:Grötschel, Martin
4353:10.1002/rsa.20770
4025:10.1002/nav.20231
3467:Chudnovsky, Maria
3002:Chudnovsky, Maria
2828:Chudnovsky, Maria
2764:separation oracle
2746:{\displaystyle v}
2726:{\displaystyle v}
2700:{\displaystyle v}
2677:{\displaystyle v}
2542:indicator vectors
2534:integral polytope
2470:{\displaystyle x}
2450:{\displaystyle A}
2427:{\displaystyle c}
2402:{\displaystyle A}
2375:{\displaystyle c}
2351:{\displaystyle b}
2331:{\displaystyle A}
2296:{\displaystyle c}
2276:{\displaystyle b}
2256:{\displaystyle A}
2217:{\displaystyle x}
2197:{\displaystyle c}
2177:{\displaystyle b}
2153:{\displaystyle A}
2049:{\displaystyle x}
2011:Cartesian product
1958:Strong perfection
1940:elimination order
1807:{\displaystyle H}
1787:{\displaystyle H}
1767:{\displaystyle H}
1752:Hamiltonian cycle
1740:{\displaystyle n}
1720:{\displaystyle n}
1634:{\displaystyle y}
1614:{\displaystyle x}
1594:{\displaystyle y}
1574:{\displaystyle x}
1500:{\displaystyle y}
1480:{\displaystyle x}
1434:{\displaystyle n}
1414:{\displaystyle 1}
1395:permutation graph
1187:{\displaystyle y}
1167:{\displaystyle x}
957:{\displaystyle x}
807:{\displaystyle G}
717:{\displaystyle G}
668:{\displaystyle G}
648:{\displaystyle G}
628:{\displaystyle G}
579:{\displaystyle G}
527:{\displaystyle G}
432:maximum matchings
285:(the size of its
274:{\displaystyle G}
254:{\displaystyle G}
229:asserts that the
25:The graph of the
5524:
5491:Perfect Problems
5455:
5454:
5444:
5415:
5409:
5408:
5390:
5378:
5372:
5371:
5336:; Liu, Xinming;
5326:
5320:
5319:
5298:
5292:
5287:Second edition,
5286:
5257:
5251:
5249:
5214:
5205:
5204:
5165:
5152:
5151:
5110:
5101:
5100:
5082:
5058:
5052:
5051:
5026:(1–3): 197–216.
5013:
5007:
5006:
4968:
4962:
4961:
4932:Tolerance graphs
4920:
4914:
4913:
4891:
4885:
4884:
4860:
4854:
4853:
4851:
4825:
4819:
4818:
4796:
4790:
4789:
4787:
4786:
4772:
4766:
4765:
4739:
4731:Heggernes, Pinar
4727:
4721:
4720:
4702:
4672:
4663:
4662:
4621:
4615:
4614:
4604:
4578:
4572:
4571:
4533:
4524:
4523:
4503:
4497:
4496:
4463:
4457:
4456:
4417:
4411:
4410:
4390:
4381:
4380:
4346:
4326:
4320:
4319:
4274:Steger, Angelika
4269:
4263:
4262:
4232:
4226:
4225:
4184:
4178:
4177:
4139:
4133:
4132:
4109:Roberts, Fred S.
4105:
4099:
4098:
4061:Pinter, Ron Yair
4052:
4046:
4045:
4027:
3990:
3984:
3983:
3965:
3928:
3922:
3921:
3903:
3874:
3868:
3867:
3818:
3809:
3808:
3781:
3775:
3774:
3732:
3726:
3725:
3672:
3666:
3665:
3624:
3618:
3617:
3571:
3558:
3557:
3542:
3536:
3535:
3533:
3532:
3518:
3512:
3511:
3479:
3463:
3457:
3456:
3454:
3453:
3442:
3436:
3435:
3397:
3391:
3390:
3388:
3387:
3377:
3369:
3363:
3362:
3344:
3318:
3305:
3295:
3289:
3288:
3277:
3271:
3270:
3255:
3249:
3248:
3215:(3–4): 395–434.
3199:
3193:
3191:
3169:
3163:
3162:
3140:
3129:
3128:
3087:
3074:
3073:
3039:
2998:
2989:
2988:
2970:
2951:
2942:
2941:
2900:
2891:
2890:
2848:
2824:
2801:claw-free graphs
2778:Related concepts
2752:
2750:
2749:
2744:
2732:
2730:
2729:
2724:
2706:
2704:
2703:
2698:
2683:
2681:
2680:
2675:
2650:ellipsoid method
2640:
2638:
2637:
2632:
2620:
2618:
2617:
2612:
2604:
2603:
2594:
2531:
2529:
2528:
2523:
2502:
2500:
2499:
2494:
2476:
2474:
2473:
2468:
2456:
2454:
2453:
2448:
2433:
2431:
2430:
2425:
2408:
2406:
2405:
2400:
2381:
2379:
2378:
2373:
2357:
2355:
2354:
2349:
2337:
2335:
2334:
2329:
2302:
2300:
2299:
2294:
2282:
2280:
2279:
2274:
2262:
2260:
2259:
2254:
2223:
2221:
2220:
2215:
2203:
2201:
2200:
2195:
2183:
2181:
2180:
2175:
2159:
2157:
2156:
2151:
2139:
2137:
2136:
2131:
2110:
2108:
2107:
2102:
2084:
2082:
2081:
2076:
2055:
2053:
2052:
2047:
1989:that is neither
1952:tolerance graphs
1944:linear extension
1928:universal vertex
1920:threshold graphs
1901:Ptolemaic graphs
1854:
1840:
1813:
1811:
1810:
1805:
1793:
1791:
1790:
1785:
1773:
1771:
1770:
1765:
1746:
1744:
1743:
1738:
1726:
1724:
1723:
1718:
1644:trapezoid graphs
1640:
1638:
1637:
1632:
1620:
1618:
1617:
1612:
1600:
1598:
1597:
1592:
1580:
1578:
1577:
1572:
1560:
1558:
1557:
1552:
1506:
1504:
1503:
1498:
1486:
1484:
1483:
1478:
1466:
1464:
1463:
1458:
1440:
1438:
1437:
1432:
1420:
1418:
1417:
1412:
1379:Mirsky's theorem
1371:
1369:
1368:
1363:
1339:
1337:
1336:
1331:
1296:linearly ordered
1273:
1271:
1270:
1265:
1249:
1247:
1246:
1241:
1223:
1221:
1220:
1215:
1193:
1191:
1190:
1185:
1173:
1171:
1170:
1165:
1153:
1151:
1150:
1145:
1127:
1125:
1124:
1119:
1101:
1099:
1098:
1093:
1071:
1069:
1068:
1063:
1045:
1043:
1042:
1037:
1019:
1017:
1016:
1011:
989:
987:
986:
981:
963:
961:
960:
955:
939:
937:
936:
931:
883:triangular books
880:
878:
877:
872:
870:
869:
842:
840:
839:
834:
813:
811:
810:
805:
789:
787:
786:
781:
779:
778:
750:Vizing's theorem
723:
721:
720:
715:
703:
701:
700:
695:
674:
672:
671:
666:
654:
652:
651:
646:
634:
632:
631:
626:
614:
612:
611:
606:
585:
583:
582:
577:
565:
563:
562:
557:
533:
531:
530:
525:
505:maximum matching
489:bipartite graphs
448:Mirsky's theorem
420:bipartite graphs
400:claw-free graphs
384:Maria Chudnovsky
380:logical matrices
280:
278:
277:
272:
260:
258:
257:
252:
231:complement graph
212:induced subgraph
207:chromatic number
195:undirected graph
158:complement graph
156:states that the
131:Mirsky's theorem
119:minimax theorems
92:induced subgraph
84:chromatic number
65:
63:
62:
57:
55:
54:
5532:
5531:
5527:
5526:
5525:
5523:
5522:
5521:
5507:
5506:
5464:
5459:
5458:
5435:(1–3): 87–147.
5416:
5412:
5388:
5379:
5375:
5327:
5323:
5316:
5299:
5295:
5283:
5258:
5254:
5215:
5208:
5166:
5155:
5114:Chvátal, Václav
5111:
5104:
5059:
5055:
5014:
5010:
4969:
4965:
4950:
4921:
4917:
4892:
4888:
4861:
4857:
4826:
4822:
4815:10.1137/0201013
4797:
4793:
4784:
4782:
4774:
4773:
4769:
4737:
4728:
4724:
4677:Chartrand, Gary
4675:Kay, David C.;
4673:
4666:
4622:
4618:
4579:
4575:
4534:
4527:
4504:
4500:
4493:
4464:
4460:
4418:
4414:
4391:
4384:
4327:
4323:
4270:
4266:
4233:
4229:
4185:
4181:
4140:
4136:
4106:
4102:
4053:
4049:
3991:
3987:
3929:
3925:
3875:
3871:
3840:10.2307/2316481
3819:
3812:
3782:
3778:
3755:
3733:
3729:
3673:
3669:
3625:
3621:
3572:
3561:
3543:
3539:
3530:
3528:
3520:
3519:
3515:
3492:
3477:
3464:
3460:
3451:
3449:
3444:
3443:
3439:
3398:
3394:
3385:
3383:
3375:
3371:
3370:
3366:
3319:
3308:
3296:
3292:
3278:
3274:
3256:
3252:
3200:
3196:
3170:
3166:
3141:
3132:
3089:
3088:
3077:
3006:Robertson, Neil
2999:
2992:
2952:
2945:
2902:
2901:
2894:
2846:
2832:Robertson, Neil
2825:
2814:
2809:
2780:
2738:
2735:
2734:
2718:
2715:
2714:
2707:from the graph.
2692:
2689:
2688:
2669:
2666:
2665:
2626:
2623:
2622:
2599:
2595:
2590:
2585:
2582:
2581:
2570:polynomial time
2554:
2508:
2505:
2504:
2482:
2479:
2478:
2462:
2459:
2458:
2442:
2439:
2438:
2419:
2416:
2415:
2394:
2391:
2390:
2367:
2364:
2363:
2360:all-ones vector
2343:
2340:
2339:
2323:
2320:
2319:
2317:(0, 1) matrices
2309:integrality gap
2288:
2285:
2284:
2268:
2265:
2264:
2248:
2245:
2244:
2234:polynomial time
2209:
2206:
2205:
2189:
2186:
2185:
2169:
2166:
2165:
2145:
2142:
2141:
2116:
2113:
2112:
2090:
2087:
2086:
2064:
2061:
2060:
2041:
2038:
2037:
2019:
1968:maximal cliques
1960:
1936:greedy coloring
1924:isolated vertex
1909:windmill graphs
1848:
1838:
1820:
1799:
1796:
1795:
1779:
1776:
1775:
1759:
1756:
1755:
1732:
1729:
1728:
1712:
1709:
1708:
1693:unipolar graphs
1672:
1664:maximal cliques
1626:
1623:
1622:
1606:
1603:
1602:
1586:
1583:
1582:
1566:
1563:
1562:
1540:
1537:
1536:
1533:interval orders
1529:interval graphs
1492:
1489:
1488:
1472:
1469:
1468:
1446:
1443:
1442:
1426:
1423:
1422:
1406:
1403:
1402:
1345:
1342:
1341:
1307:
1304:
1303:
1259:
1256:
1255:
1229:
1226:
1225:
1203:
1200:
1199:
1179:
1176:
1175:
1159:
1156:
1155:
1133:
1130:
1129:
1107:
1104:
1103:
1081:
1078:
1077:
1051:
1048:
1047:
1025:
1022:
1021:
999:
996:
995:
969:
966:
965:
949:
946:
945:
925:
922:
921:
899:
865:
861:
859:
856:
855:
819:
816:
815:
799:
796:
795:
774:
770:
768:
765:
764:
741:chromatic index
709:
706:
705:
680:
677:
676:
660:
657:
656:
640:
637:
636:
620:
617:
616:
591:
588:
587:
571:
568:
567:
542:
539:
538:
519:
516:
515:
509:Kőnig's theorem
476:
428:Kőnig's theorem
416:minimax theorem
412:
368:Fulkerson Prize
344:Kőnig's theorem
340:bipartite graph
328:
266:
263:
262:
246:
243:
242:
235:independent set
178:
168:, leading to a
139:Kőnig's theorem
115:polynomial time
44:
40:
38:
35:
34:
17:
12:
11:
5:
5530:
5520:
5519:
5517:Perfect graphs
5505:
5504:
5495:
5487:
5477:
5474:Václav Chvátal
5463:
5462:External links
5460:
5457:
5456:
5419:Faudree, Ralph
5410:
5373:
5354:(2): 143–186.
5321:
5314:
5302:Lovász, László
5293:
5281:
5252:
5222:Lovász, László
5206:
5173:Lovász, László
5153:
5126:(2): 138–154.
5102:
5053:
5008:
4981:(3): 302–312.
4963:
4948:
4915:
4904:(2): 217–227.
4886:
4875:(4): 445–463.
4863:Hoáng, C. T.;
4855:
4842:(1–2): 85–99.
4820:
4809:(2): 180–187.
4791:
4767:
4722:
4664:
4637:(3): 163–174.
4625:Corneil, D. G.
4616:
4595:(2): 125–133.
4573:
4546:(2): 182–208.
4525:
4498:
4491:
4458:
4431:(1–2): 71–76.
4412:
4401:(3): 597–609.
4382:
4337:(1): 148–186.
4321:
4264:
4245:(3): 275–284.
4227:
4200:(1): 105–107.
4179:
4152:(3): 309–316.
4134:
4100:
4047:
4018:(5): 530–543.
3985:
3923:
3878:Perfect, Hazel
3869:
3834:(8): 876–877.
3810:
3776:
3753:
3727:
3692:(4): 453–465.
3667:
3619:
3584:(2): 255–259.
3559:
3537:
3513:
3490:
3458:
3437:
3392:
3364:
3306:
3290:
3272:
3250:
3194:
3182:(1): 180–196.
3164:
3153:(2): 209–212.
3130:
3091:Lovász, László
3075:
2990:
2943:
2916:(3): 253–267.
2904:Lovász, László
2892:
2811:
2810:
2808:
2805:
2779:
2776:
2760:
2759:
2756:
2755:
2754:
2742:
2722:
2711:
2708:
2696:
2673:
2630:
2610:
2607:
2602:
2598:
2593:
2589:
2553:
2550:
2521:
2518:
2515:
2512:
2492:
2489:
2486:
2466:
2446:
2423:
2412:maximal clique
2398:
2387:Václav Chvátal
2371:
2347:
2327:
2292:
2272:
2252:
2213:
2193:
2173:
2160:is given as a
2149:
2129:
2126:
2123:
2120:
2100:
2097:
2094:
2074:
2071:
2068:
2045:
2031:canonical form
2018:
2015:
1972:Meyniel graphs
1959:
1956:
1932:
1931:
1916:
1897:
1857:
1856:
1829:chordal graphs
1819:
1816:
1803:
1783:
1763:
1736:
1716:
1671:
1668:
1630:
1610:
1590:
1570:
1550:
1547:
1544:
1521:interval graph
1496:
1487:occurs before
1476:
1456:
1453:
1450:
1430:
1410:
1361:
1358:
1355:
1352:
1349:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1276:family of sets
1263:
1239:
1236:
1233:
1213:
1210:
1207:
1183:
1163:
1143:
1140:
1137:
1117:
1114:
1111:
1091:
1088:
1085:
1061:
1058:
1055:
1035:
1032:
1029:
1009:
1006:
1003:
979:
976:
973:
953:
929:
898:
895:
891:skew partition
868:
864:
853:complete graph
832:
829:
826:
823:
803:
777:
773:
737:maximum degree
713:
693:
690:
687:
684:
664:
644:
624:
604:
601:
598:
595:
575:
555:
552:
549:
546:
523:
475:
472:
468:Meyniel graphs
464:chordal graphs
411:
408:
388:Neil Robertson
327:
324:
315:induced cycles
289:), equals its
270:
250:
203:graph coloring
177:
174:
88:maximum clique
53:
50:
47:
43:
15:
9:
6:
4:
3:
2:
5529:
5518:
5515:
5514:
5512:
5503:
5502:perfect graph
5499:
5496:
5493:
5492:
5488:
5485:
5481:
5478:
5475:
5471:
5470:
5466:
5465:
5452:
5448:
5443:
5438:
5434:
5430:
5429:
5424:
5420:
5414:
5406:
5402:
5398:
5394:
5387:
5383:
5377:
5369:
5365:
5361:
5357:
5353:
5349:
5348:
5347:Combinatorica
5343:
5339:
5338:Seymour, Paul
5335:
5331:
5325:
5317:
5315:0-12-086202-6
5311:
5307:
5303:
5297:
5290:
5284:
5282:0-444-51530-5
5278:
5274:
5270:
5266:
5262:
5256:
5247:
5243:
5239:
5235:
5231:
5227:
5223:
5219:
5213:
5211:
5202:
5198:
5194:
5190:
5186:
5182:
5178:
5174:
5170:
5164:
5162:
5160:
5158:
5149:
5145:
5141:
5137:
5133:
5129:
5125:
5121:
5120:
5115:
5109:
5107:
5098:
5094:
5090:
5086:
5081:
5076:
5072:
5068:
5064:
5057:
5049:
5045:
5041:
5037:
5033:
5029:
5025:
5021:
5020:
5012:
5004:
5000:
4996:
4992:
4988:
4984:
4980:
4976:
4975:
4967:
4959:
4955:
4951:
4949:0-521-82758-2
4945:
4941:
4937:
4933:
4929:
4928:Trenk, Ann N.
4925:
4919:
4911:
4907:
4903:
4899:
4898:
4890:
4882:
4878:
4874:
4870:
4866:
4859:
4850:
4845:
4841:
4837:
4836:
4831:
4824:
4816:
4812:
4808:
4804:
4803:
4795:
4781:
4777:
4771:
4763:
4759:
4755:
4751:
4747:
4743:
4736:
4732:
4726:
4718:
4714:
4710:
4706:
4701:
4696:
4692:
4688:
4687:
4682:
4678:
4671:
4669:
4660:
4656:
4652:
4648:
4644:
4640:
4636:
4632:
4631:
4626:
4620:
4612:
4608:
4603:
4598:
4594:
4590:
4589:
4584:
4577:
4569:
4565:
4561:
4557:
4553:
4549:
4545:
4541:
4540:
4532:
4530:
4521:
4517:
4513:
4509:
4502:
4494:
4492:9783540378099
4488:
4484:
4480:
4476:
4472:
4471:Bari, Ruth A.
4468:
4467:Harary, Frank
4462:
4454:
4450:
4446:
4442:
4438:
4434:
4430:
4426:
4422:
4416:
4408:
4404:
4400:
4396:
4389:
4387:
4378:
4374:
4370:
4366:
4362:
4358:
4354:
4350:
4345:
4340:
4336:
4332:
4325:
4317:
4313:
4309:
4305:
4301:
4297:
4293:
4289:
4285:
4281:
4280:
4275:
4268:
4260:
4256:
4252:
4248:
4244:
4240:
4239:
4238:Combinatorica
4231:
4223:
4219:
4215:
4211:
4207:
4203:
4199:
4195:
4194:
4189:
4183:
4175:
4171:
4167:
4163:
4159:
4155:
4151:
4147:
4146:
4138:
4130:
4126:
4122:
4118:
4114:
4110:
4104:
4096:
4092:
4088:
4084:
4080:
4076:
4072:
4068:
4067:
4062:
4058:
4051:
4043:
4039:
4035:
4031:
4026:
4021:
4017:
4013:
4012:
4007:
4003:
3999:
3995:
3989:
3981:
3977:
3973:
3969:
3964:
3959:
3955:
3951:
3950:
3945:
3941:
3937:
3933:
3927:
3919:
3915:
3911:
3907:
3902:
3897:
3893:
3889:
3888:
3883:
3879:
3873:
3865:
3861:
3857:
3853:
3849:
3845:
3841:
3837:
3833:
3829:
3828:
3823:
3817:
3815:
3806:
3802:
3798:
3794:
3790:
3786:
3785:Berge, Claude
3780:
3772:
3768:
3764:
3760:
3756:
3754:0-387-24219-8
3750:
3746:
3742:
3738:
3731:
3723:
3719:
3715:
3711:
3707:
3703:
3699:
3695:
3691:
3687:
3686:
3681:
3677:
3671:
3663:
3659:
3655:
3651:
3647:
3643:
3639:
3635:
3634:
3629:
3623:
3615:
3611:
3607:
3603:
3599:
3595:
3591:
3587:
3583:
3579:
3578:
3570:
3568:
3566:
3564:
3555:
3551:
3547:
3541:
3527:
3523:
3517:
3509:
3505:
3501:
3497:
3493:
3491:0-521-61523-2
3487:
3483:
3476:
3472:
3471:Seymour, Paul
3468:
3462:
3447:
3441:
3433:
3429:
3425:
3421:
3417:
3413:
3409:
3405:
3404:
3396:
3381:
3374:
3368:
3360:
3356:
3352:
3348:
3343:
3338:
3334:
3330:
3329:
3324:
3317:
3315:
3313:
3311:
3303:
3299:
3294:
3286:
3282:
3281:Berge, Claude
3276:
3268:
3264:
3260:
3259:Berge, Claude
3254:
3246:
3242:
3238:
3234:
3230:
3226:
3222:
3218:
3214:
3210:
3209:
3204:
3203:Gallai, Tibor
3198:
3189:
3185:
3181:
3177:
3176:
3168:
3160:
3156:
3152:
3148:
3147:
3146:Combinatorica
3139:
3137:
3135:
3126:
3122:
3118:
3114:
3110:
3106:
3102:
3098:
3097:
3092:
3086:
3084:
3082:
3080:
3071:
3067:
3063:
3059:
3055:
3051:
3047:
3043:
3038:
3033:
3030:(1): 51–229.
3029:
3025:
3024:
3019:
3015:
3014:Thomas, Robin
3011:
3010:Seymour, Paul
3007:
3003:
2997:
2995:
2986:
2982:
2978:
2974:
2969:
2964:
2960:
2956:
2950:
2948:
2939:
2935:
2931:
2927:
2923:
2919:
2915:
2911:
2910:
2905:
2899:
2897:
2888:
2884:
2880:
2876:
2872:
2868:
2864:
2860:
2856:
2852:
2845:
2841:
2840:Thomas, Robin
2837:
2836:Seymour, Paul
2833:
2829:
2823:
2821:
2819:
2817:
2812:
2804:
2802:
2797:
2791:
2789:
2785:
2775:
2773:
2767:
2765:
2757:
2753:to the graph.
2740:
2720:
2712:
2709:
2694:
2686:
2685:
2671:
2663:
2662:
2661:
2657:
2655:
2651:
2646:
2644:
2628:
2608:
2605:
2600:
2596:
2591:
2587:
2579:
2575:
2574:Lovász number
2571:
2567:
2563:
2559:
2549:
2547:
2543:
2539:
2535:
2519:
2516:
2513:
2510:
2490:
2487:
2484:
2464:
2444:
2437:For a matrix
2435:
2421:
2413:
2396:
2388:
2383:
2369:
2361:
2345:
2325:
2318:
2314:
2310:
2306:
2290:
2270:
2250:
2241:
2239:
2235:
2231:
2227:
2211:
2191:
2171:
2163:
2147:
2127:
2124:
2121:
2118:
2098:
2095:
2092:
2072:
2069:
2066:
2059:
2043:
2036:
2033:as seeking a
2032:
2028:
2024:
2014:
2012:
2007:
2006:induced paths
2003:
1996:
1992:
1988:
1983:
1979:
1977:
1973:
1969:
1965:
1955:
1953:
1949:
1945:
1941:
1937:
1929:
1925:
1921:
1917:
1914:
1910:
1906:
1902:
1898:
1895:
1891:
1887:
1883:
1879:
1874:
1870:
1869:
1866:
1861:
1852:
1846:
1842:
1835:
1830:
1826:
1825:
1824:
1815:
1801:
1781:
1761:
1753:
1748:
1734:
1714:
1706:
1702:
1698:
1697:cluster graph
1694:
1689:
1681:
1676:
1667:
1665:
1661:
1660:ordered trees
1657:
1653:
1649:
1645:
1628:
1608:
1588:
1568:
1548:
1545:
1542:
1534:
1530:
1522:
1517:
1513:
1511:
1494:
1474:
1454:
1451:
1448:
1428:
1408:
1400:
1396:
1387:
1383:
1380:
1376:
1356:
1353:
1350:
1324:
1321:
1318:
1315:
1312:
1301:
1297:
1293:
1287:
1285:
1281:
1277:
1261:
1253:
1237:
1234:
1231:
1211:
1208:
1205:
1197:
1181:
1161:
1141:
1138:
1135:
1115:
1112:
1109:
1089:
1086:
1083:
1075:
1059:
1056:
1053:
1033:
1030:
1027:
1007:
1004:
1001:
993:
992:antisymmetric
977:
974:
971:
951:
943:
927:
919:
912:
908:
907:Hasse diagram
903:
894:
892:
886:
884:
866:
862:
854:
850:
846:
827:
821:
801:
775:
771:
762:
757:
753:
751:
747:
742:
738:
733:
731:
727:
726:rook's graphs
711:
688:
682:
662:
642:
622:
599:
593:
573:
550:
544:
537:
521:
512:
510:
506:
502:
498:
497:median graphs
494:
490:
480:
471:
469:
465:
461:
457:
453:
449:
445:
441:
437:
436:vertex covers
433:
429:
425:
421:
417:
407:
405:
401:
397:
393:
389:
385:
381:
377:
373:
369:
364:
363:László Lovász
359:
357:
353:
349:
345:
341:
337:
333:
323:
319:
316:
312:
308:
303:
299:
294:
292:
288:
284:
268:
248:
240:
236:
232:
228:
219:
215:
213:
208:
204:
200:
199:clique number
196:
192:
182:
173:
171:
167:
163:
159:
155:
150:
148:
144:
140:
136:
132:
128:
124:
123:combinatorics
120:
116:
112:
108:
104:
100:
95:
93:
89:
85:
82:in which the
81:
77:
76:perfect graph
73:
51:
48:
45:
41:
32:
28:
23:
19:
5490:
5468:
5432:
5426:
5413:
5396:
5392:
5376:
5351:
5345:
5324:
5305:
5296:
5288:
5264:
5255:
5229:
5184:
5123:
5117:
5062:
5056:
5023:
5017:
5011:
4978:
4972:
4966:
4931:
4918:
4901:
4895:
4889:
4872:
4868:
4858:
4839:
4833:
4823:
4806:
4800:
4794:
4783:. Retrieved
4779:
4770:
4745:
4741:
4725:
4690:
4684:
4634:
4628:
4619:
4592:
4586:
4576:
4543:
4542:. Series B.
4537:
4511:
4501:
4474:
4461:
4428:
4424:
4421:Dirac, G. A.
4415:
4398:
4394:
4334:
4330:
4324:
4286:(1): 53–79.
4283:
4277:
4267:
4242:
4236:
4230:
4197:
4191:
4182:
4149:
4143:
4137:
4112:
4103:
4073:(1): 35–46.
4070:
4064:
4055:Dagan, Ido;
4050:
4015:
4009:
3988:
3953:
3947:
3926:
3894:(1): 19–22.
3891:
3885:
3872:
3831:
3825:
3822:Mirsky, Leon
3788:
3779:
3737:Ordered Sets
3736:
3730:
3689:
3683:
3676:Kőnig, Dénes
3670:
3637:
3631:
3622:
3581:
3575:
3553:
3549:
3546:Kőnig, Dénes
3540:
3529:. Retrieved
3525:
3516:
3481:
3461:
3450:. Retrieved
3440:
3410:(5578): 38.
3407:
3401:
3395:
3384:. Retrieved
3379:
3367:
3332:
3326:
3293:
3284:
3275:
3266:
3262:
3253:
3212:
3206:
3197:
3179:
3173:
3167:
3150:
3144:
3103:(2): 95–98.
3100:
3099:. Series B.
3094:
3037:math/0212070
3027:
3021:
2968:math/0304464
2958:
2913:
2907:
2854:
2850:
2792:
2781:
2768:
2761:
2658:
2647:
2578:unit vectors
2555:
2536:. It is the
2436:
2384:
2242:
2226:real numbers
2020:
2002:parity graph
1999:
1987:parity graph
1975:
1961:
1939:
1933:
1913:block graphs
1881:
1877:
1850:
1821:
1749:
1700:
1692:
1685:
1526:
1392:
1294:, and it is
1288:
1283:
1252:incomparable
1251:
1195:
1154:). Elements
915:
887:
793:
734:
513:
501:vertex cover
486:
413:
396:Robin Thomas
392:Paul Seymour
360:
356:Berge graphs
355:
348:Claude Berge
332:Tibor Gallai
329:
320:
306:
302:cycle graphs
295:
281:itself, the
239:clique cover
224:
188:
151:
125:, including
96:
75:
72:graph theory
69:
27:3-3 duoprism
18:
5382:Gyárfás, A.
4865:Reed, B. A.
4693:: 342–346.
3956:: 160–175.
2538:convex hull
1882:false twins
1688:split graph
1680:split graph
1399:permutation
746:Dénes Kőnig
424:line graphs
5246:0634.05001
5148:0277.05139
5097:0910.05028
5048:0933.05144
5003:0634.05058
4785:2023-02-12
4762:1169.68653
4717:0139.17301
4659:0463.05057
4611:0382.05045
4568:0605.05024
4377:1405.05165
4344:1604.00890
4316:0793.05063
4222:0384.05057
4174:0495.05027
4129:0193.24205
4095:0658.05067
4042:1143.90337
3980:0204.24604
3936:Lempel, A.
3932:Pnueli, A.
3918:0428.06001
3864:0263.06002
3805:0203.26403
3771:1072.06001
3706:46.0146.03
3662:1103.05034
3614:0366.05043
3556:: 116–119.
3531:2023-01-24
3508:1109.05092
3452:2023-01-21
3386:2023-01-21
3359:1104.05029
3245:0084.19603
3125:0241.05107
3070:1112.05042
2985:1004.05034
2938:0239.05111
2887:1028.05035
2807:References
2552:Algorithms
1878:true twins
1705:Almost all
1652:semiorders
1196:comparable
1074:transitive
536:line graph
456:antichains
422:and their
336:complement
145:, and the
31:line graph
4453:120608513
3722:121097364
3628:Boros, E.
3432:116891342
3237:123953062
3062:119151552
2784:χ-bounded
2629:θ
2609:θ
2606:
2517:≤
2488:≥
2125:≤
2096:≥
2070:⋅
1995:bipartite
1970:. In the
1845:treewidth
1546:≤
1467:whenever
1452:≤
1300:antichain
1262:⊆
1235:≤
1209:≤
1139:≤
1113:≤
1087:≤
1031:≤
1005:≤
975:≤
942:reflexive
928:≤
430:relating
307:anticycle
143:matchings
99:colorings
5511:Category
5384:(1987).
5263:(1980).
5228:(1988).
5179:(1984).
4930:(2004).
4679:(1965).
4369:53489550
4308:28696495
3942:(1971).
3940:Even, S.
3880:(1980).
3678:(1916).
3606:38906333
3473:(2005).
3424:12098683
3016:(2006).
2842:(2003).
2788:identity
2621:, where
2532:form an
2140:. Here,
940:that is
185:perfect.
5451:1432221
5405:0951359
5368:2229369
5238:0936633
5201:0778770
5140:0371732
5089:1635464
5040:1708837
4995:0888682
4958:2051713
4754:2460558
4709:0175113
4651:0619603
4560:0859310
4520:0505860
4445:0130190
4361:3884617
4300:1167295
4259:0637832
4214:0522739
4166:0666799
4121:0252267
4087:0953414
4034:2335544
3972:0292717
3910:0558270
3856:0288054
3848:2316481
3797:0232694
3763:2127991
3714:1511872
3654:2261906
3598:0457293
3500:2187738
3403:Science
3351:2261918
3229:0124238
3117:0309780
3054:2233847
2977:1957560
2930:0302480
2879:5226655
2871:2004404
2540:of the
2358:is the
2238:NP-hard
1886:cograph
1128:, then
1046:, then
483:vertex.
326:History
5449:
5403:
5366:
5312:
5279:
5244:
5236:
5199:
5146:
5138:
5095:
5087:
5046:
5038:
5001:
4993:
4956:
4946:
4760:
4752:
4715:
4707:
4657:
4649:
4609:
4566:
4558:
4518:
4489:
4451:
4443:
4375:
4367:
4359:
4314:
4306:
4298:
4257:
4220:
4212:
4172:
4164:
4127:
4119:
4093:
4085:
4040:
4032:
3978:
3970:
3916:
3908:
3862:
3854:
3846:
3803:
3795:
3769:
3761:
3751:
3720:
3712:
3704:
3660:
3652:
3612:
3604:
3596:
3506:
3498:
3488:
3430:
3422:
3357:
3349:
3269:: 114.
3243:
3235:
3227:
3123:
3115:
3068:
3060:
3052:
2983:
2975:
2936:
2928:
2885:
2877:
2869:
2564:, and
2546:facets
2283:, and
2164:, and
2162:matrix
2035:vector
1841:-trees
1278:. The
1250:, and
1072:, and
881:, and
452:chains
404:Hajnal
394:, and
193:in an
191:clique
109:, and
5389:(PDF)
5364:S2CID
4738:(PDF)
4449:S2CID
4365:S2CID
4339:arXiv
4304:S2CID
3844:JSTOR
3718:S2CID
3602:S2CID
3478:(PDF)
3428:S2CID
3376:(PDF)
3233:S2CID
3058:S2CID
3032:arXiv
2963:arXiv
2875:S2CID
2847:(PDF)
2772:co-NP
1754:. If
1292:chain
843:is a
493:trees
338:of a
80:graph
78:is a
29:(the
5310:ISBN
5277:ISBN
4944:ISBN
4487:ISBN
3749:ISBN
3486:ISBN
3420:PMID
2652:for
2184:and
2111:and
2025:and
1993:nor
1962:The
1918:The
1871:The
1853:+ 1)
1827:The
1527:The
1194:are
1174:and
1102:and
1076:(if
1020:and
994:(if
905:The
495:and
454:and
446:and
434:and
374:and
296:The
225:The
152:The
129:and
74:, a
5472:by
5437:doi
5433:164
5356:doi
5269:doi
5242:Zbl
5189:doi
5144:Zbl
5128:doi
5093:Zbl
5075:hdl
5067:doi
5044:Zbl
5028:doi
4999:Zbl
4983:doi
4936:doi
4906:doi
4877:doi
4844:doi
4811:doi
4758:Zbl
4713:Zbl
4695:doi
4655:Zbl
4639:doi
4607:Zbl
4597:doi
4564:Zbl
4548:doi
4479:doi
4433:doi
4403:doi
4373:Zbl
4349:doi
4312:Zbl
4288:doi
4247:doi
4218:Zbl
4202:doi
4170:Zbl
4154:doi
4125:Zbl
4091:Zbl
4075:doi
4038:Zbl
4020:doi
3976:Zbl
3958:doi
3914:Zbl
3896:doi
3860:Zbl
3836:doi
3801:Zbl
3767:Zbl
3741:doi
3702:JFM
3694:doi
3658:Zbl
3642:doi
3638:306
3610:Zbl
3586:doi
3504:Zbl
3412:doi
3408:297
3355:Zbl
3337:doi
3333:306
3241:Zbl
3217:doi
3184:doi
3155:doi
3121:Zbl
3105:doi
3066:Zbl
3042:doi
3028:164
2981:Zbl
2934:Zbl
2918:doi
2883:Zbl
2859:doi
2597:cos
2385:As
1974:or
1621:to
1519:An
1421:to
1224:or
1198:if
990:),
487:In
458:in
450:on
141:on
133:on
121:in
70:In
33:of
5513::
5500::
5447:MR
5445:.
5431:.
5425:.
5401:MR
5397:19
5395:.
5362:.
5352:25
5350:.
5340:;
5332:;
5275:.
5240:.
5234:MR
5224:;
5220:;
5209:^
5197:MR
5195:.
5175:;
5171:;
5156:^
5142:.
5136:MR
5134:.
5124:18
5122:.
5105:^
5091:.
5085:MR
5083:.
5073:.
5042:.
5036:MR
5034:.
5024:95
5022:.
4997:.
4991:MR
4989:.
4979:42
4977:.
4954:MR
4952:.
4942:.
4926:;
4902:12
4900:.
4873:13
4871:.
4840:27
4838:.
4832:.
4805:.
4778:.
4756:.
4750:MR
4746:14
4744:.
4740:.
4711:.
4705:MR
4703:.
4691:17
4689:.
4683:.
4667:^
4653:.
4647:MR
4645:.
4633:.
4605:.
4593:24
4591:.
4585:.
4562:.
4556:MR
4554:.
4544:41
4528:^
4516:MR
4485:.
4447:.
4441:MR
4439:.
4429:25
4427:.
4399:32
4397:.
4385:^
4371:.
4363:.
4357:MR
4355:.
4347:.
4335:54
4333:.
4310:.
4302:.
4296:MR
4294:.
4282:.
4255:MR
4253:.
4241:.
4216:.
4210:MR
4208:.
4198:24
4196:.
4168:.
4162:MR
4160:.
4148:.
4123:.
4117:MR
4089:.
4083:MR
4081:.
4071:21
4069:.
4059:;
4036:.
4030:MR
4028:.
4016:54
4014:.
4008:.
4000:;
3996:;
3974:.
3968:MR
3966:.
3954:23
3952:.
3946:.
3938:;
3934:;
3912:.
3906:MR
3904:.
3892:21
3890:.
3884:.
3858:.
3852:MR
3850:.
3842:.
3832:78
3830:.
3813:^
3799:.
3793:MR
3765:.
3759:MR
3757:.
3747:.
3716:.
3710:MR
3708:.
3700:.
3690:77
3688:.
3682:.
3656:.
3650:MR
3648:.
3636:.
3608:.
3600:.
3594:MR
3592:.
3582:12
3580:.
3562:^
3554:38
3552:.
3524:.
3502:.
3496:MR
3494:.
3480:.
3469:;
3426:.
3418:.
3406:.
3353:.
3347:MR
3345:.
3331:.
3325:.
3309:^
3267:10
3265:.
3239:.
3231:.
3225:MR
3223:.
3211:.
3178:.
3151:16
3149:.
3133:^
3119:.
3113:MR
3111:.
3101:13
3078:^
3064:.
3056:.
3050:MR
3048:.
3040:.
3026:.
3020:.
3012:;
3008:;
3004:;
2993:^
2979:.
2973:MR
2971:.
2946:^
2932:.
2926:MR
2924:.
2912:.
2895:^
2881:.
2873:.
2867:MR
2865:.
2855:97
2853:.
2849:.
2838:;
2834:;
2830:;
2815:^
2803:.
2766:.
2560:,
2503:,
2434:.
2263:,
2240:.
2000:A
1985:A
1703:.
1686:A
1666:.
1512:.
1393:A
964:,
916:A
893:.
759:A
752:.
511:.
466:,
390:,
386:,
358:.
189:A
137:,
105:,
5486:.
5476:.
5453:.
5439::
5407:.
5370:.
5358::
5318:.
5285:.
5271::
5248:.
5203:.
5191::
5150:.
5130::
5099:.
5077::
5069::
5050:.
5030::
5005:.
4985::
4960:.
4938::
4912:.
4908::
4883:.
4879::
4852:.
4846::
4817:.
4813::
4807:1
4788:.
4764:.
4719:.
4697::
4661:.
4641::
4635:3
4613:.
4599::
4570:.
4550::
4522:.
4495:.
4481::
4455:.
4435::
4409:.
4405::
4379:.
4351::
4341::
4318:.
4290::
4284:1
4261:.
4249::
4243:1
4224:.
4204::
4176:.
4156::
4150:6
4131:.
4097:.
4077::
4044:.
4022::
3982:.
3960::
3920:.
3898::
3866:.
3838::
3807:.
3773:.
3743::
3724:.
3696::
3664:.
3644::
3616:.
3588::
3534:.
3510:.
3455:.
3434:.
3414::
3389:.
3361:.
3339::
3247:.
3219::
3213:9
3190:.
3186::
3180:6
3161:.
3157::
3127:.
3107::
3072:.
3044::
3034::
2987:.
2965::
2940:.
2920::
2914:2
2889:.
2861::
2741:v
2721:v
2695:v
2672:v
2601:2
2592:/
2588:1
2520:1
2514:x
2511:A
2491:0
2485:x
2465:x
2445:A
2422:c
2397:A
2370:c
2346:b
2326:A
2291:c
2271:b
2251:A
2212:x
2192:c
2172:b
2148:A
2128:b
2122:x
2119:A
2099:0
2093:x
2073:x
2067:c
2044:x
1896:.
1876:(
1851:k
1849:(
1839:k
1802:H
1782:H
1762:H
1735:n
1715:n
1629:y
1609:x
1589:y
1569:x
1549:y
1543:x
1495:y
1475:x
1455:y
1449:x
1429:n
1409:1
1360:}
1357:D
1354:,
1351:C
1348:{
1328:}
1325:C
1322:,
1319:B
1316:,
1313:A
1310:{
1238:x
1232:y
1212:y
1206:x
1182:y
1162:x
1142:z
1136:x
1116:z
1110:y
1090:y
1084:x
1060:y
1057:=
1054:x
1034:x
1028:y
1008:y
1002:x
978:x
972:x
952:x
867:4
863:K
831:)
828:G
825:(
822:L
802:G
776:4
772:K
712:G
692:)
689:G
686:(
683:L
663:G
643:G
623:G
603:)
600:G
597:(
594:L
574:G
554:)
551:G
548:(
545:L
522:G
269:G
249:G
52:3
49:,
46:3
42:K
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
