Perfect graph (original) (raw)

About DBpedia

In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt. Ein induzierter Subgraph eines Graphen besteht dabei aus einer Teilmenge der Knoten und allen inzidenten Kanten.

thumbnail

Property Value
dbo:abstract In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt. Ein induzierter Subgraph eines Graphen besteht dabei aus einer Teilmenge der Knoten und allen inzidenten Kanten. (de) En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo. En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos. Los grafos perfectos incluyen varias familias de grafos importantes, y sirven para unificar resultados relacionados con la coloración y los cliques en esas familias. Por ejemplo, en todos los grafos perfectos, el problema de coloración de grafos, el y el pueden ser resueltos en tiempo polinómico. Además, varios teoremas min-max importantes de combinatoria como el , pueden ser expresados en términos de la perfección de ciertos grafos asociados. La teoría de grafos perfectos fue desarrollada a partir de un resultado obtenido en 1958 por que en lenguaje moderno puede ser interpretado de modo que el complementario de un grafo bipartito es perfecto. Este resultado puede ser visto también como un equivalente simple del teorema de König, un resultado anterior que relaciona emparejamientos con cobertura de vértices en grafos bipartitos. El primer uso de la frase "grafo perfecto" parece estar en un paper de 1963 publicado por Claude Berge. En este paper, Berge unió el resultado de Gallai con varios otros resultados similares, definiendo los grafos perfectos y conjeturando una caracterización de esos grafos que luego fue probado como el Teorema fuerte de los grafos perfectos. (es) En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égale à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait. (fr) In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have . 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. A graph is 1-perfect if and only if . Then, is perfect if and only if every induced subgraph of is 1-perfect. (en) グラフ理論で、パーフェクトグラフ（英: perfect graph）とは、すべての誘導部分グラフの彩色数とが等しいグラフである。「理想グラフ」あるいは「完璧グラフ」と和訳されることもある。 (ja) 그래프 이론에서 완벽 그래프(영어: perfect graph)는 그 색칠수가 클릭과 특별한 관계를 만족시키는 그래프이다. (ko) Een perfecte graaf is een graaf waarvan voor elke geïnduceerde subgraaf geldt dat het cliquegetal gelijk is aan het chromatisch getal van die subgraaf. Een geïnduceerde subgraaf bestaat uit een deelverzameling van de knopen van de graaf en alleen de zijden van de graaf tussen die knopen. Het cliquegetal is het aantal knopen in de grootste volledige subgraaf van een graaf. De naam perfecte graaf wordt toegeschreven aan de Franse wiskundige Claude Berge die die in 1963 in een artikel gebruikte. Men kan in polynomiale tijd bepalen of een gegeven graaf een perfecte graaf is en ook in polynomiale tijd van een perfecte graaf het chromatisch getal, cliquegetal of stabiliteitsgetal berekenen, terwijl dit in het algemene geval een NP-compleet probleem is. Er komen in de grafentheorie verschillende perfecte grafen voor, bijvoorbeeld: * bipartiete grafen * chordale grafen * volledige grafen (nl) Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più grande di quel sottografo. Grazie al , sappiamo dal 2002 che i grafi perfetti sono la stessa cosa dei grafi di Berge. Un grafo G è un grafo di Berge se né G né il suo complemento hanno un di lunghezza dispari uguale a 5 o superiore. I grafi perfetti comprendono molte importanti famiglie di grafi, e servono a unificare risultati che collegano le colorazioni e le cricche in quelle famiglie. Per esempio, in tutti i grafi perfetti, il problema della colorazione dei grafi, il problema della cricca massima e il problema del massimo insieme indipendente possono essere tutti risolti in tempo polinomiale. In aggiunta, parecchi importanti teoremi di minimo e massimo in combinatoria, come il , possono essere espressi in termini della perfezione di certi grafi associati. La teoria dei grafi perfetti si sviluppò da un risultato del 1958 di Tibor Gallai che in linguaggio moderno può essere interpretato affermando che il complemento di un grafo bipartito è perfetto; questo risultato può anche essere visto come un semplice equivalente del , un risultato molto anteriore che collega gli accoppiamenti e le coperture dei vertici nei grafi bipartiti. Il primo uso della locuzione "grafo perfetto" pare che sia in un saggio del 1963 di , dal quale prendono nome i grafi di Berge. In questo saggio egli unificò il risultato di Gallai con vari risultati simili definendo i grafi perfetti, e congetturò l'equivalenza delle definizioni di grafo perfetto e di grafo di Berge; la congettura di Berge fu dimostrata nel 2002 come il . (it) Graf doskonały (ang. perfect graph) – graf w którym liczba chromatyczna każdego podgrafu indukowanego (wierzchołkowo) jest równa rozmiarowi największej kliki tego podgrafu. W każdym grafie rozmiar kliki jest dolnym ograniczeniem na liczbę chromatyczną, ponieważ przy kolorowaniu każdy wierzchołek kliki musi otrzymać inny kolor. W grafach doskonałych to ograniczenie jest ścisłe, nie tylko dla samego grafu ale również dla wszystkich jego podgrafów. Dla innych grafów nie musi tak być: przykładowo cykl długości 5 ma liczbę chromatyczną 3, choć rozmiar największej kliki wynosi 2. Wiele istotnych klas grafów jest grafami doskonałymi, co umożliwia znalezienie łatwych rozwiązań dla niektórych problemów trudnych w ogólności. Przykładowo problem kolorowania grafów, problem kliki i problem maksymalnego zbioru niezależnego mają rozwiązania działające dla wszystkich grafów doskonałych w wielomianowym czasie. Przykładowe klasy grafów doskonałych to: * grafy dwudzielne * grafy krawędziowe uzyskane z grafów dwudzielnych * grafy przedziałowe (pl) Em teoria dos grafos, um grafo perfeito é um grafo em que o número cromático de cada subgrafo induzido é igual ao tamanho da maior clique deste subgrafo. Em qualquer grafo, o número de clique fornece um limite inferior para o número cromático, assim como todos os vértices em uma clique devem ser atribuídos cores distintas em qualquer coloração adequada. Os grafos perfeitos são aqueles para os quais este limite inferior é apertado, não apenas no grafo em si, mas em todos os seus subgrafos induzidos. Para grafos de forma mais geral, o número cromático e o número da clique podem diferir; por exemplo, um ciclo de comprimento 5, requer três cores em qualquer coloração adequada, mas a sua maior clique tem tamanho 2. Grafos perfeitos incluem muitas famílias importantes de grafos, e servem para unificar os resultados relativos a colorações e cliques nessas famílias. Por exemplo, em todos os grafos perfeitos, o problema da coloração de grafos, o e o problema do conjunto independente máximo podem ser resolvidos em . Além disso, vários teoremas importantes min-max em análise combinatória, como o , podem ser expressos em termos da perfeição de alguns grafos associados. A teoria dos grafos perfeitos desenvolveu-se a partir um resultado de 1958 de Tibor Gallai que em linguagem moderna, pode ser interpretado como indicando que o complementar de um grafo bipartido é perfeito; este resultado também pode ser visto como um simples equivalente do , um resultado bem mais anterior relacionando acoplamentos e coberturas de vértices em grafos bipartidos. O primeiro uso da expressão "grafo perfeito" parece estar em um artigo de 1963 de Claude Berge. Neste artigo ele unificou o resultado de Gallai com vários resultados semelhantes através da definição de grafos perfeitos e conjecturando uma caracterização destes grafos que mais tarde foi comprovado como o Teorema Forte dos Grafos Perfeitos. (pt) Досконалим графом називається граф, у якому хроматичне число будь-якого породженого підграфу дорівнює розміру максимальної кліки цього підграфу. Відповідно до сильної теореми про досконалі графи, досконалі графи — це те саме, що й графи Берже. Граф G є графом Берже, якщо ні G, ні його додаток не мають породжених циклів, довжиною більше 5 ребер. Досконалий граф містить у собі багато досконалих сімейств графів, та забезпечують уніфікацію результатів, пов'язаних із розфарбуванням та кліками цих сімейств. Наприклад, для всіх досконалих графів задача про розфарбовування , задача про максимальну кліку та задача про максимальну незалежну множину можуть бути розв'язані за поліномінальний час. Крім того, декілька важливих мінімаксних теорем комбінаторики, такі як теорема Ділуорса, можуть бути виражені в термінах досконалих та деяких пов'язаних з ними графів. Теорія досконалих графів почала свій розвиток після роботи Тібора Галаї 1958 року, що може бути інтерпретована на сучасній мові як твердження: доповнення двочасткового графу є досконалим графом. Також це можна розглядати як простий еквівалент до теореми Кьоніга, а значно раніший результат стосується паросполучень та покриття вершин у двочасткових графах. Вперше словосполучення «досконалий граф» було вжите в 1963 році у статті Клауді Бержа, після якого було інтерпретоване як «граф Берже». У цій статті вчений пов'язав результати Галая з деякими іншими шляхом визначення досконалих графів та запропонував гіпотезу про ідентичність досконалих графів та «графів Берже», що була доведена в 2002 році як сильна теорема про досконалі графи. (uk) В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины (5 и более рёбер). Совершенные графы включают много важных семейств графов и обеспечивают унификацию результатов, связанных с раскраской и кликами этих семейств. Например, во всех совершенных графах задача раскраски, задача о максимальной клике и задача о максимальном независимом множестве могут быть решены за полиномиальное время. Вдобавок, некоторые важные минимаксные теоремы комбинаторики, такие как теорема Дилуорса, могут быть сформулированы в терминах совершенных и некоторых связанных с ними графов. Теория совершенных графов развивается с работы 1958-го года , которая на современном языке может быть интерпретирована как утверждение, что дополнение двудольного графа есть совершенный граф. Этот результат можно рассматривать как простой эквивалент теоремы Кёнига, значительно более ранний результат относительно паросочетаний и вершинных покрытий в двудольных графах. Первое применение термина «совершенный граф» появилось в 1963 году в статье , откуда и появилось название «графы Бержа». В этой статье он объединил результат Галаи с некоторыми похожими результатами путём определения совершенных графов и высказал гипотезу об эквивалентности совершенных графов и графов Бержа. Гипотеза доказана в 2002 году как строгая теорема о совершенных графах. (ru)
dbo:thumbnail wiki-commons:Special:FilePath/Paley9-perfect.svg?width=300
dbo:wikiPageExternalLink http://www.graphclasses.org/index.html http://www.cs.concordia.ca/~chvatal/perfect/problems.html http://www.aimath.org/WWN/perfectgraph/ http://annals.princeton.edu/annals/2006/164-1/p02.xhtml http://www.cs.concordia.ca/~chvatal/perfect/spgt.html http://www.graphclasses.org/classes/gc_56.html http://www.elsevier.com/wps/find/bookdescription.cws_home/699916/description%23description https://web.archive.org/web/20100522154759/http:/www.elsevier.com/wps/find/bookdescription.cws_home/699916/description%23description
dbo:wikiPageID 670531 (xsd:integer)
dbo:wikiPageLength 17165 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1081261925 (xsd:integer)
dbo:wikiPageWikiLink dbr:American_Institute_of_Mathematics dbr:Robin_Thomas_(mathematician) dbr:Rook's_graph dbr:Mirsky's_theorem dbr:András_Hajnal dbr:Annals_of_Mathematics dbr:Antichain dbc:Perfect_graphs dbr:Paul_Seymour_(mathematician) dbr:Vizing's_theorem dbr:Induced_path dbr:Induced_subgraph dbr:Kőnig's_theorem_(graph_theory) dbr:Ptolemaic_graph dbr:Ptolemy's_inequality dbr:Complete_bipartite_graph dbr:Ellipsoid_method dbr:Claude_Berge dbr:Co-NP dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:Erdős–Szekeres_theorem dbr:Line_graph dbr:Lovász_number dbr:László_Lovász dbr:Claw-free_graph dbr:Clique_(graph_theory) dbr:Clique_number dbr:Combinatorica dbr:Combinatorics dbr:Comparability_graph dbr:Complement_graph dbr:Tibor_Gallai dbr:Tree_(graph_theory) dbr:Treewidth dbr:Trivially_perfect_graph dbr:Václav_Chvátal dbr:Wheel_graph dbr:Windmill_graph dbr:K-tree dbr:Linear_programming dbr:Trapezoid_graph dbr:Edge_coloring dbr:Forbidden_graph_characterization dbr:Partially_ordered_set dbr:Dilworth's_theorem dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Acta_Mathematica_Academiae_Scientiarum_Hungaricae dbr:Intersection_graph dbr:Interval_graph dbr:Chordal_graph dbr:Bipartite_graph dbr:Block_graph dbr:Cograph dbr:Threshold_graph dbr:Trapezoid dbr:Distance-hereditary_graph dbr:Maria_Chudnovsky dbr:Split_graph dbr:Greedy_coloring dbr:Polynomial_time dbr:Graph_coloring_problem dbr:Maximum_clique_problem dbr:Maximum_matching dbr:Neil_Robertson_(mathematician) dbr:Longest_increasing_subsequence dbr:Strong_perfect_graph_theorem dbr:Strongly_chordal_graph dbr:Perfect_graph_theorem dbr:Perfectly_orderable_graph dbr:Permutation_graph dbr:Induced_cycle dbr:Maximum_independent_set_problem dbr:Semidefinite_program dbr:File:7-hole_and_antihole.svg dbr:File:Paley9-perfect.svg
dbp:wikiPageUsesTemplate dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Harv dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description
dct:subject dbc:Perfect_graphs
gold:hypernym dbr:Graph
rdf:type dbo:Software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659
rdfs:comment In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt. Ein induzierter Subgraph eines Graphen besteht dabei aus einer Teilmenge der Knoten und allen inzidenten Kanten. (de) En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égale à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait. (fr) グラフ理論で、パーフェクトグラフ（英: perfect graph）とは、すべての誘導部分グラフの彩色数とが等しいグラフである。「理想グラフ」あるいは「完璧グラフ」と和訳されることもある。 (ja) 그래프 이론에서 완벽 그래프(영어: perfect graph)는 그 색칠수가 클릭과 특별한 관계를 만족시키는 그래프이다. (ko) En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo. En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos. (es) In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have . A graph is 1-perfect if and only if . Then, is perfect if and only if every induced subgraph of is 1-perfect. (en) Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più grande di quel sottografo. Grazie al , sappiamo dal 2002 che i grafi perfetti sono la stessa cosa dei grafi di Berge. Un grafo G è un grafo di Berge se né G né il suo complemento hanno un di lunghezza dispari uguale a 5 o superiore. (it) Een perfecte graaf is een graaf waarvan voor elke geïnduceerde subgraaf geldt dat het cliquegetal gelijk is aan het chromatisch getal van die subgraaf. Een geïnduceerde subgraaf bestaat uit een deelverzameling van de knopen van de graaf en alleen de zijden van de graaf tussen die knopen. Het cliquegetal is het aantal knopen in de grootste volledige subgraaf van een graaf. De naam perfecte graaf wordt toegeschreven aan de Franse wiskundige Claude Berge die die in 1963 in een artikel gebruikte. Er komen in de grafentheorie verschillende perfecte grafen voor, bijvoorbeeld: (nl) В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины (5 и более рёбер). (ru) Graf doskonały (ang. perfect graph) – graf w którym liczba chromatyczna każdego podgrafu indukowanego (wierzchołkowo) jest równa rozmiarowi największej kliki tego podgrafu. W każdym grafie rozmiar kliki jest dolnym ograniczeniem na liczbę chromatyczną, ponieważ przy kolorowaniu każdy wierzchołek kliki musi otrzymać inny kolor. W grafach doskonałych to ograniczenie jest ścisłe, nie tylko dla samego grafu ale również dla wszystkich jego podgrafów. Dla innych grafów nie musi tak być: przykładowo cykl długości 5 ma liczbę chromatyczną 3, choć rozmiar największej kliki wynosi 2. (pl) Em teoria dos grafos, um grafo perfeito é um grafo em que o número cromático de cada subgrafo induzido é igual ao tamanho da maior clique deste subgrafo. Em qualquer grafo, o número de clique fornece um limite inferior para o número cromático, assim como todos os vértices em uma clique devem ser atribuídos cores distintas em qualquer coloração adequada. Os grafos perfeitos são aqueles para os quais este limite inferior é apertado, não apenas no grafo em si, mas em todos os seus subgrafos induzidos. Para grafos de forma mais geral, o número cromático e o número da clique podem diferir; por exemplo, um ciclo de comprimento 5, requer três cores em qualquer coloração adequada, mas a sua maior clique tem tamanho 2. (pt) Досконалим графом називається граф, у якому хроматичне число будь-якого породженого підграфу дорівнює розміру максимальної кліки цього підграфу. Відповідно до сильної теореми про досконалі графи, досконалі графи — це те саме, що й графи Берже. Граф G є графом Берже, якщо ні G, ні його додаток не мають породжених циклів, довжиною більше 5 ребер. (uk)
rdfs:label Perfekter Graph (de) Grafo perfecto (es) Graphe parfait (fr) Grafo perfetto (it) パーフェクトグラフ (ja) 완벽 그래프 (ko) Perfecte graaf (nl) Perfect graph (en) Graf doskonały (pl) Grafo perfeito (pt) Совершенный граф (ru) Досконалий граф (uk)
owl:sameAs freebase:Perfect graph wikidata:Perfect graph dbpedia-de:Perfect graph dbpedia-es:Perfect graph dbpedia-fa:Perfect graph dbpedia-fr:Perfect graph dbpedia-he:Perfect graph dbpedia-hu:Perfect graph dbpedia-it:Perfect graph dbpedia-ja:Perfect graph dbpedia-ko:Perfect graph dbpedia-nl:Perfect graph dbpedia-pl:Perfect graph dbpedia-pt:Perfect graph dbpedia-ru:Perfect graph dbpedia-sr:Perfect graph dbpedia-uk:Perfect graph https://global.dbpedia.org/id/Eygq yago-res:Perfect graph
prov:wasDerivedFrom wikipedia-en:Perfect_graph?oldid=1081261925&ns=0
foaf:depiction wiki-commons:Special:FilePath/7-hole_and_antihole.svg wiki-commons:Special:FilePath/Paley9-perfect.svg
foaf:isPrimaryTopicOf wikipedia-en:Perfect_graph
is dbo:wikiPageDisambiguates of dbr:Perfect
is dbo:wikiPageRedirects of dbr:Odd_antihole dbr:Odd_hole dbr:Berge_graph
is dbo:wikiPageWikiLink of dbr:Rook's_graph dbr:List_of_conjectures dbr:Mirsky's_theorem dbr:Open-shop_scheduling dbr:Parity_graph dbr:List_of_graph_theory_topics dbr:Pathwidth dbr:Paul_Seymour_(mathematician) dbr:Cycle_(graph_theory) dbr:Independent_set_(graph_theory) dbr:Indifference_graph dbr:Induced_matching dbr:Induced_path dbr:Induced_subgraph dbr:Kőnig's_theorem_(graph_theory) dbr:Lexicographic_product_of_graphs dbr:Ptolemaic_graph dbr:Zero-divisor_graph dbr:148_(number) dbr:Matching_in_hypergraphs dbr:Neighbourhood_(graph_theory) dbr:Skew_partition dbr:Claude_Berge dbr:Clique_problem dbr:Endre_Boros dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:Erdős–Hajnal_conjecture dbr:Martin_Charles_Golumbic dbr:Line_graph dbr:Line_perfect_graph dbr:Lovász_number dbr:Claw-free_graph dbr:Clique_(graph_theory) dbr:Clique_cover dbr:Comparability_graph dbr:Complement_graph dbr:Franklin_graph dbr:Fulkerson_Prize dbr:Helly_family dbr:Kristina_Vušković dbr:Perfect dbr:Meyniel_graph dbr:Bruce_Reed_(mathematician) dbr:Trivially_perfect_graph dbr:Wheel_graph dbr:Dually_chordal_graph dbr:Gérard_Cornuéjols dbr:Trapezoid_graph dbr:Forbidden_graph_characterization dbr:Dilworth's_theorem dbr:Discrete_Mathematics_(journal) dbr:Folkman_graph dbr:Goldner–Harary_graph dbr:Graph_property dbr:Graph_theory dbr:Reconstruction_conjecture dbr:Interval_graph dbr:Uniquely_colorable_graph dbr:Tolerance_graph dbr:Chordal_graph dbr:Bipartite_graph dbr:Block_graph dbr:Cograph dbr:Herschel_graph dbr:Hoffman_graph dbr:Distance-hereditary_graph dbr:Maria_Chudnovsky dbr:Polygon_covering dbr:Split_graph dbr:Circular-arc_graph dbr:Greedy_coloring dbr:Neil_Robertson_(mathematician) dbr:Strong_perfect_graph_theorem dbr:Möbius–Kantor_graph dbr:Polygon-circle_graph dbr:Perfect_graph_theorem dbr:Perfectly_orderable_graph dbr:Permutation_graph dbr:Χ-bounded dbr:Property_testing dbr:Odd_antihole dbr:Odd_hole dbr:Berge_graph
is dbp:properties of dbr:Rook's_graph dbr:Franklin_graph dbr:Folkman_graph dbr:Goldner–Harary_graph dbr:Herschel_graph dbr:Hoffman_graph dbr:Möbius–Kantor_graph
is foaf:primaryTopic of wikipedia-en:Perfect_graph