گراف تام: تفاوت میان نسخه‌ها

از ویکی‌پدیا، دانشنامهٔ آزاد
نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
Forough94 (بحث | مشارکت‌ها)
۱۱ ویرایش‌ها
بدون خلاصۀ ویرایش
Forough94 (بحث | مشارکت‌ها)
۱۱ ویرایش‌ها
بدون خلاصۀ ویرایش
خط ۱: خط ۱:
[[Image:Paley9-perfect.svg|thumb|240px|The [[Paley graph]] of order 9, colored with three colors and showing a clique of three vertices. In this graph and each of its induced subgraphs the chromatic number equals the clique number, so it is a perfect graph.]]
در تئوری گراف ، یک گراف آرمانی گرافی است که عدد فامی هر زیر گراف القایی ، برابر سایز بزرگترین گروه آن زیرگراف باشد. در سایه ی تئوری قوی گراف آرمانی ، از سال 2002 میدانیم که گراف های آرمانی همانند گراف های برگ هستند. گراف G یک گراف برگ است اگر خود گراف G یا مکملش یک دورالقایی به طول فرد حداقل 5 داشته باشد.
در [[تئوری گراف]] ، یک گراف آرمانی گرافی است که عدد فامی هر زیر گراف القایی ، برابر سایز بزرگترین گروه آن زیرگراف باشد. در سایه ی تئوری قوی گراف آرمانی ، از سال 2002 میدانیم که گراف های آرمانی همانند گراف های برگ هستند. گراف G یک گراف برگ است اگر خود گراف G یا مکملش یک دورالقایی به طول فرد حداقل 5 داشته باشد.
گراف های آرمانی دربرگیرنده ی تعداد زیادی دسته های مهم گراف ها هستند و در یکی کردن نتایج مربوط به رنگ آمیزی ها و گروه ها در آن دسته ها ، بکار میروند. بعنوان مثال در همه ی گراف های آرمانی مسئله ی رنگ آمیزی گراف ، مسئله ی بزرگترین گروه و مسئله ی بزرگترین مجموعه ی مستقل همگی در زمان چند جمله ای بدست می آیند.علاوه بر این ، برخی از تئوری های مهم کوچکترین-بزرگترین در ترکیبات ، مانند تئوری Dilworth میتوانند در قالب ایده آل کردن گراف متناظرشان بیان شوند.
In [[graph theory]], a '''perfect graph''' is a [[graph (mathematics)|graph]] in which the [[Graph coloring|chromatic number]] of every [[induced subgraph]] equals the size of the largest [[Clique (graph theory)|clique]] of that subgraph. Thanks to the [[strong perfect graph theorem]], we have known since 2002 that perfect graphs are the same as '''Berge graphs'''. A graph G is a Berge graph if neither G nor its complement has an odd-length [[induced cycle]] of length 5 or more.
نظریه‌ی گراف ایده‌آل از سال ۱۹۵۸ به وسیله‌ی Tibor Gallai گسترش پیدا کرد، نتیجه‌ی کار او را می‌توان اینگونه تعبیر کرد که مکمل یک گراف دوبخشی ایده آل است؛ این نتیجه نیز می تواند به عنوان یک معادل ساده از نظریه König دانست . برآمدی خیلی قدیمی تر که با تطابق و پوشش راسی در گراف های دو بخشی مرتبط بود. اولین استفاده ی واژه ی گراف آرمانی به نظر می رسد در یک مقاله 1963 از کلود برگ است و پس از آن گراف برگ نامیده شد. در این مقاله او نتیجه ی Gallai را با برخی از نتایج مشابه ، بوسیله تعریف گراف آرمانی یکی کرد و برابری گراف ایده آل و گراف برگ را حدس زد.حدس برگ در سال 2002 بعنوان نظریه ی قوی گراف آرمانی ثابت شده است .

The perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families. For instance, in all perfect graphs, the [[graph coloring problem]], [[maximum clique problem]], and [[maximum independent set problem]] can all be solved in [[polynomial time]]. In addition, several important min-max theorems in [[combinatorics]], such as [[Dilworth's theorem]], can be expressed in terms of the perfection of certain associated graphs.

The theory of perfect graphs developed from a 1958 result of [[Tibor Gallai]] that in modern language can be interpreted as stating that the [[complement graph|complement]] of a [[bipartite graph]] is perfect; this result can also be viewed as a simple equivalent of [[König's theorem (graph theory)|König's theorem]], a much earlier result relating matchings and vertex covers in bipartite graphs. The first use of the phrase "perfect graph" appears to be in a 1963 paper of [[Claude Berge]], after whom Berge graphs are named. In this paper he unified Gallai's result with several similar results by defining perfect graphs, and he conjectured the equivalence of the perfect graph and Berge graph definitions; Berge's conjecture was proved in 2002 as the [[strong perfect graph theorem]].

==Families of graphs that are perfect==
Some of the more well-known perfect graphs are:
* [[Bipartite graph]]s, the graphs that can be [[graph coloring|colored]] with two colors, including the [[Tree (graph theory)|forests]], graphs with no cycles.
* The [[line graph]]s of bipartite graphs (see [[König's theorem (graph theory)|König's theorem]]). The [[rook's graph]]s (line graphs of [[complete bipartite graph]]s) are a special case.
* [[Chordal graph]]s, the graphs in which every cycle of four or more vertices has a ''chord'', an edge between two vertices that are not consecutive in the cycle. These include the forests, [[K-tree|''k''-trees]] (maximal graphs with a given [[treewidth]]), [[split graph]]s (graphs that can be partitioned into a clique and an independent set), [[block graph]]s (graphs in which every biconnected component is a clique), [[interval graph]]s (graphs in which each vertex represents an interval of a line and each edge represents a nonempty intersection between two intervals), [[trivially perfect graph]]s (interval graphs for nested intervals), [[threshold graph]]s (graphs in which two vertices are adjacent when their total weight exceeds a numerical threshold), [[windmill graph]]s (formed by joining equal cliques at a common vertex), and [[strongly chordal graph]]s (chordal graphs in which every even cycle of length six or more has an odd chord).
* [[Comparability graph]]s formed from [[partially ordered set]]s by connecting pairs of elements by an edge whenever they are related in the partial order. These include the bipartite graphs, the complements of interval graphs, the trivially perfect graphs, the threshold graphs, the windmill graphs, the [[permutation graph]]s (graphs in which the edges represent pairs of elements that are reversed by a permutation), and the [[cograph]]s (graphs formed by recursive operations of disjoint union and complementation).
* [[Perfectly orderable graph]]s, the graphs that can be ordered in such a way that a [[greedy coloring]] algorithm is optimal on every induced subgraph. These include the bipartite graphs, the chordal graphs, the comparability graphs, the [[distance-hereditary graph]]s (in which shortest path distances in connected induced subgraphs equal those in the whole graph), and the [[wheel graph]]s that have an odd number of vertices.
* [[Trapezoid graph]]s, the [[intersection graph]]s of [[trapezoid]]s whose parallel pairs of edges lie on two parallel lines. These include the interval graphs, trivially perfect graphs, threshold graphs, windmill graphs, and permutation graphs; their complements are a subset of the comparability graphs.

==Relation to min-max theorems==
In all graphs, the clique number provides a lower bound for the chromatic number, as all vertices in a clique must be assigned distinct colors in any proper coloring. The perfect graphs are those for which this lower bound is tight, not just in the graph itself but in all of its induced subgraphs. For graphs that are not perfect, the chromatic number and clique number can differ; for instance, a cycle of length five requires three colors in any proper coloring but its largest clique has size two.

A proof that a class of graphs is perfect can be seen as a min-max theorem: the minimum number of colors needed for these graphs equals the maximum size of a clique. Many important min-max theorems in combinatorics can be expressed in these terms. For instance, [[Dilworth's theorem]] states that the minimum number of chains in a partition of a [[partially ordered set]] into chains equals the maximum size of an [[antichain]], and can be rephrased as stating that the complements of [[comparability graph]]s are perfect. [[Mirsky's theorem]] states that the minimum number of antichains into a partition into antichains equals the maximum size of a chain, and corresponds in the same way to the perfection of comparability graphs.

The perfection of [[permutation graph]]s is equivalent to the statement that, in every sequence of ordered elements, the length of the [[Longest increasing subsequence|longest decreasing subsequence]] equals the minimum number of sequences in a partition into increasing subsequences. The [[Erdős–Szekeres theorem]] is an easy consequence of this statement.

[[König's theorem (graph theory)|König's theorem]] in graph theory states that a minimum vertex cover in a bipartite graph corresponds to a [[maximum matching]], and vice versa; it can be interpreted as the perfection of the complements of bipartite graphs. Another theorem about bipartite graphs, that their [[edge coloring|chromatic index]] [[Vizing's theorem|equals their maximum degree]], is equivalent to the perfection of the line graphs of bipartite graphs.

==Characterizations and the perfect graph theorems==
In his initial work on perfect graphs, Berge made two important conjectures on their structure that were only proved later.

The first of these two theorems was the [[perfect graph theorem]] of [[László_Lovász|Lovász]] (1972), stating that a graph is perfect if and only if its [[complement graph|complement]] is perfect. Thus, perfection (defined as the equality of maximum clique size and chromatic number in every induced subgraph) is equivalent to the equality of maximum independent set size and clique cover number.

[[File:7-hole and antihole.svg|thumb|240px|A seven-vertex cycle and its complement, showing in each case an optimal coloring and a maximum clique (shown with heavy edges). Since neither graph uses a number of colors equal to its clique size, neither is perfect.]]
The second theorem, conjectured by Berge, provided a [[forbidden graph characterization]] of the perfect graphs.
An [[induced path|induced cycle]] of odd length at least 5 is called an '''odd hole'''. An induced subgraph that is the complement of an odd hole is called an '''odd antihole'''. An odd cycle of length greater than 3 cannot be perfect, because its chromatic number is three and its clique number is two. Similarly, the complement of an odd cycle of length 2''k'' + 1 cannot be perfect, because its chromatic number is ''k'' + 1 and its clique number is ''k''. (Alternatively, the imperfection of this graph follows from the perfect graph theorem and the imperfection of the complementary odd cycle). Because these graphs are not perfect, every perfect graph must be a '''Berge graph''', a graph with no odd holes and no odd antiholes. Berge conjectured the converse, that every Berge graph is perfect. This was finally proven as the [[strong perfect graph theorem]] of [[Maria Chudnovsky|Chudnovsky]], [[Neil Robertson (mathematician)|Robertson]], [[Paul Seymour (mathematician)|Seymour]], and [[Robin Thomas (mathematician)|Thomas]] (2006).

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 [[claw-free graph]]s.

==Algorithms on perfect graphs==
In all perfect graphs, the [[graph coloring problem]], [[maximum clique problem]], and [[maximum independent set problem]] can all be solved in [[polynomial time]] {{harv|Grötschel|Lovász|Schrijver|1988}}. The algorithm for the general case involves the use of the [[ellipsoid method]] for [[linear programming]], but more efficient combinatorial algorithms are known for many special cases.

For many years the complexity of recognizing Berge graphs and perfect graphs remained open. From the definition of Berge graphs, it follows immediately that their recognition is in [[co-NP]] (Lovász 1983). Finally, subsequent to the proof of the strong perfect graph theorem, a polynomial time algorithm was discovered by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković.

== References ==
* {{cite journal
| author = Berge, Claude
| authorlink = Claude Berge
| year = 1961
| title = Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind
| journal = Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe
| volume = 10
| pages = 114
| ref = harv}}
* {{cite conference
| author = Berge, Claude
| authorlink = Claude Berge
| year = 1963
| title = Perfect graphs
| booktitle = Six Papers on Graph Theory
| publisher = Indian Statistical Institute
| location = Calcutta
| pages = 1–21}}
* {{cite journal
| author = [[Maria Chudnovsky|Chudnovsky, Maria]]; Cornuéjols, Gérard; Liu, Xinming; [[Paul Seymour (mathematician)|Seymour, Paul]]; Vušković, Kristina
| year = 2005
| title = Recognizing Berge graphs
| journal = Combinatorica
| volume = 25
| issue = 2
| pages = 143–186
| doi = 10.1007/s00493-005-0012-8
| ref = harv}}
* {{cite journal
| author = [[Maria Chudnovsky|Chudnovsky, Maria]]; [[Neil Robertson (mathematician)|Robertson, Neil]]; [[Paul Seymour (mathematician)|Seymour, Paul]]; [[Robin Thomas (mathematician)|Thomas, Robin]]
| year = 2006
| url = http://annals.princeton.edu/annals/2006/164-1/p02.xhtml
| title = The strong perfect graph theorem
| journal = [[Annals of Mathematics]]
| volume = 164 | issue = 1
| pages = 51–229
| doi = 10.4007/annals.2006.164.51
| ref = harv}}
* {{cite journal
| author = Gallai, Tibor
| authorlink = Tibor Gallai
| title = Maximum-minimum Sätze über Graphen
| year = 1958
| journal = Acta Math. Acad. Sci. Hungar.
| volume = 9
| issue = 3-4
| pages = 395–434
| doi = 10.1007/BF02020271
| ref = harv}}
* {{Cite document
| author = Golumbic, Martin Charles
| authorlink = Martin Charles Golumbic
| title = Algorithmic Graph Theory and Perfect Graphs
| publisher = Academic Press
| year = 1980
| id = ISBN 0-444-51530-5
| url = http://www.elsevier.com/wps/find/bookdescription.cws_home/699916/description#description
| ref = harv
| postscript = <!--None-->
}} Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
* {{Cite document
| last1 = Grötschel | first1 = Martin
| first2 = László | last2 = Lovász | authorlink2 = László Lovász
| first3 = Alexander | last3 = Schrijver | author3-link = Alexander Schrijver
| title = Geometric Algorithms and Combinatorial Optimization
| publisher = Springer-Verlag
| year = 1988
| ref = harv
| postscript = <!--None-->}}. See especially chapter 9, "Stable Sets in Graphs", pp.&nbsp;273–303.
* {{cite journal
| author = Lovász, László
| authorlink = László Lovász
| year = 1972
| title = Normal hypergraphs and the perfect graph conjecture
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
| volume = 2
| issue = 3
| pages = 253–267
| doi = 10.1016/0012-365X(72)90006-4
| ref = harv}}
* {{cite journal
| author = Lovász, László
| authorlink = László Lovász
| year = 1972
| title = A characterization of perfect graphs
| journal = Journal of Combinatorial Theory, Series B
| volume = 13
| issue = 2
| pages = 95–98
| doi = 10.1016/0095-8956(72)90045-7
| ref = harv}}
* {{cite conference
| author = Lovász, László
| authorlink = László Lovász
| year = 1983
| title = Perfect graphs
| editor = Beineke, Lowell W.; Wilson, Robin J. (Eds.)
| booktitle = Selected Topics in Graph Theory, Vol. 2
| pages = 55–87
| publisher = Academic Press
| id = ISBN 0-12-086202-6}}

== External links ==
* [http://www.cs.concordia.ca/~chvatal/perfect/spgt.html ''The Strong Perfect Graph Theorem''] by [[Václav Chvátal]].
* [http://www.aimath.org/WWN/perfectgraph/ Open problems on perfect graphs], maintained by the [[American Institute of Mathematics]].
* [http://www.cs.concordia.ca/~chvatal/perfect/problems.html ''Perfect Problems''], maintained by Václav Chvátal.
* [http://www.graphclasses.org/index.html Information System on Graph Class Inclusions]: [http://www.graphclasses.org/classes/gc_56.html perfect graph]


[[Category:Perfect graphs| ]]

نسخهٔ ‏۲۰ مهٔ ۲۰۱۴، ساعت ۱۷:۵۶

The Paley graph of order 9, colored with three colors and showing a clique of three vertices. In this graph and each of its induced subgraphs the chromatic number equals the clique number, so it is a perfect graph.

در تئوری گراف ، یک گراف آرمانی گرافی است که عدد فامی هر زیر گراف القایی ، برابر سایز بزرگترین گروه آن زیرگراف باشد. در سایه ی تئوری قوی گراف آرمانی ، از سال 2002 میدانیم که گراف های آرمانی همانند گراف های برگ هستند. گراف G یک گراف برگ است اگر خود گراف G یا مکملش یک دورالقایی به طول فرد حداقل 5 داشته باشد. In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Thanks to the strong perfect graph theorem, we have known since 2002 that perfect graphs are the same as Berge graphs. A graph G is a Berge graph if neither G nor its complement has an odd-length induced cycle of length 5 or more.

The perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families. For instance, in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time. In addition, several important min-max theorems in combinatorics, such as Dilworth's theorem, can be expressed in terms of the perfection of certain associated graphs.

The theory of perfect graphs developed from a 1958 result of Tibor Gallai that in modern language can be interpreted as stating that the complement of a bipartite graph is perfect; this result can also be viewed as a simple equivalent of König's theorem, a much earlier result relating matchings and vertex covers in bipartite graphs. The first use of the phrase "perfect graph" appears to be in a 1963 paper of Claude Berge, after whom Berge graphs are named. In this paper he unified Gallai's result with several similar results by defining perfect graphs, and he conjectured the equivalence of the perfect graph and Berge graph definitions; Berge's conjecture was proved in 2002 as the strong perfect graph theorem.

Families of graphs that are perfect

Some of the more well-known perfect graphs are:

  • Bipartite graphs, the graphs that can be colored with two colors, including the forests, graphs with no cycles.
  • The line graphs of bipartite graphs (see König's theorem). The rook's graphs (line graphs of complete bipartite graphs) are a special case.
  • Chordal graphs, the graphs in which every cycle of four or more vertices has a chord, an edge between two vertices that are not consecutive in the cycle. These include the forests, k-trees (maximal graphs with a given treewidth), split graphs (graphs that can be partitioned into a clique and an independent set), block graphs (graphs in which every biconnected component is a clique), interval graphs (graphs in which each vertex represents an interval of a line and each edge represents a nonempty intersection between two intervals), trivially perfect graphs (interval graphs for nested intervals), threshold graphs (graphs in which two vertices are adjacent when their total weight exceeds a numerical threshold), windmill graphs (formed by joining equal cliques at a common vertex), and strongly chordal graphs (chordal graphs in which every even cycle of length six or more has an odd chord).
  • Comparability graphs formed from partially ordered sets by connecting pairs of elements by an edge whenever they are related in the partial order. These include the bipartite graphs, the complements of interval graphs, the trivially perfect graphs, the threshold graphs, the windmill graphs, the permutation graphs (graphs in which the edges represent pairs of elements that are reversed by a permutation), and the cographs (graphs formed by recursive operations of disjoint union and complementation).
  • Perfectly orderable graphs, the graphs that can be ordered in such a way that a greedy coloring algorithm is optimal on every induced subgraph. These include the bipartite graphs, the chordal graphs, the comparability graphs, the distance-hereditary graphs (in which shortest path distances in connected induced subgraphs equal those in the whole graph), and the wheel graphs that have an odd number of vertices.
  • Trapezoid graphs, the intersection graphs of trapezoids whose parallel pairs of edges lie on two parallel lines. These include the interval graphs, trivially perfect graphs, threshold graphs, windmill graphs, and permutation graphs; their complements are a subset of the comparability graphs.

Relation to min-max theorems

In all graphs, the clique number provides a lower bound for the chromatic number, as all vertices in a clique must be assigned distinct colors in any proper coloring. The perfect graphs are those for which this lower bound is tight, not just in the graph itself but in all of its induced subgraphs. For graphs that are not perfect, the chromatic number and clique number can differ; for instance, a cycle of length five requires three colors in any proper coloring but its largest clique has size two.

A proof that a class of graphs is perfect can be seen as a min-max theorem: the minimum number of colors needed for these graphs equals the maximum size of a clique. Many important min-max theorems in combinatorics can be expressed in these terms. For instance, Dilworth's theorem states that the minimum number of chains in a partition of a partially ordered set into chains equals the maximum size of an antichain, and can be rephrased as stating that the complements of comparability graphs are perfect. Mirsky's theorem states that the minimum number of antichains into a partition into antichains equals the maximum size of a chain, and corresponds in the same way to the perfection of comparability graphs.

The perfection of permutation graphs is equivalent to the statement that, in every sequence of ordered elements, the length of the longest decreasing subsequence equals the minimum number of sequences in a partition into increasing subsequences. The Erdős–Szekeres theorem is an easy consequence of this statement.

König's theorem in graph theory states that a minimum vertex cover in a bipartite graph corresponds to a maximum matching, and vice versa; it can be interpreted as the perfection of the complements of bipartite graphs. Another theorem about bipartite graphs, that their chromatic index equals their maximum degree, is equivalent to the perfection of the line graphs of bipartite graphs.

Characterizations and the perfect graph theorems

In his initial work on perfect graphs, Berge made two important conjectures on their structure that were only proved later.

The first of these two theorems was the perfect graph theorem of Lovász (1972), stating that a graph is perfect if and only if its complement is perfect. Thus, perfection (defined as the equality of maximum clique size and chromatic number in every induced subgraph) is equivalent to the equality of maximum independent set size and clique cover number.

A seven-vertex cycle and its complement, showing in each case an optimal coloring and a maximum clique (shown with heavy edges). Since neither graph uses a number of colors equal to its clique size, neither is perfect.

The second theorem, conjectured by Berge, provided a forbidden graph characterization of the perfect graphs. An induced cycle of odd length at least 5 is called an odd hole. An induced subgraph that is the complement of an odd hole is called an odd antihole. An odd cycle of length greater than 3 cannot be perfect, because its chromatic number is three and its clique number is two. Similarly, the complement of an odd cycle of length 2k + 1 cannot be perfect, because its chromatic number is k + 1 and its clique number is k. (Alternatively, the imperfection of this graph follows from the perfect graph theorem and the imperfection of the complementary odd cycle). Because these graphs are not perfect, every perfect graph must be a Berge graph, a graph with no odd holes and no odd antiholes. Berge conjectured the converse, that every Berge graph is perfect. This was finally proven as the strong perfect graph theorem of Chudnovsky, Robertson, Seymour, and Thomas (2006).

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 claw-free graphs.

Algorithms on perfect graphs

In all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time (Grötschel, Lovász & Schrijver 1988). The algorithm for the general case involves the use of the ellipsoid method for linear programming, but more efficient combinatorial algorithms are known for many special cases.

For many years the complexity of recognizing Berge graphs and perfect graphs remained open. From the definition of Berge graphs, it follows immediately that their recognition is in co-NP (Lovász 1983). Finally, subsequent to the proof of the strong perfect graph theorem, a polynomial time algorithm was discovered by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković.

References

  • Berge, Claude (1961). "Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind". Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. 10: 114.
  • Berge, Claude (1963). "Perfect graphs". Six Papers on Graph Theory. Calcutta: Indian Statistical Institute. pp. 1–21. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
  • Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). "Recognizing Berge graphs". Combinatorica. 25 (2): 143–186. doi:10.1007/s00493-005-0012-8.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
  • Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics. 164 (1): 51–229. doi:10.4007/annals.2006.164.51.{{cite journal}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
  • Gallai, Tibor (1958). "Maximum-minimum Sätze über Graphen". Acta Math. Acad. Sci. Hungar. 9 (3–4): 395–434. doi:10.1007/BF02020271.
  • Golumbic, Martin Charles (1980). "Algorithmic Graph Theory and Perfect Graphs". Academic Press. ISBN 0-444-51530-5. {{cite journal}}: Cite journal requires |journal= (help) Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
  • Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988). "Geometric Algorithms and Combinatorial Optimization". Springer-Verlag. {{cite journal}}: Cite journal requires |journal= (help). See especially chapter 9, "Stable Sets in Graphs", pp. 273–303.
  • Lovász, László (1972). "Normal hypergraphs and the perfect graph conjecture". Discrete Mathematics. 2 (3): 253–267. doi:10.1016/0012-365X(72)90006-4.
  • Lovász, László (1972). "A characterization of perfect graphs". Journal of Combinatorial Theory, Series B. 13 (2): 95–98. doi:10.1016/0095-8956(72)90045-7.
  • Lovász, László (1983). "Perfect graphs". In Beineke, Lowell W.; Wilson, Robin J. (Eds.) (ed.). Selected Topics in Graph Theory, Vol. 2. Academic Press. pp. 55–87. ISBN 0-12-086202-6. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)نگهداری یادکرد:نام‌های متعدد:فهرست ویراستاران (link)

External links

برگرفته از «https://fa.wikipedia.org/w/index.php?title=گراف_تام&oldid=12620524»