About: Perfect graph

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Graph whose maximum clique’s size equals the chromatic number

Property	Value
dbo:description	Begriff aus der Graphentheorie (de) matematikai fogalom a gráfelméletben (hu) סוג גרף (iw) grafik türü (tr) grafo, kies maksimuma kliko estas tiel granda kiel la kolora nombro (eo) граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа (ru) graph whose maximum clique’s size equals the chromatic number (en) گراف کامل (fa)
dbo:thumbnail	wiki-commons:Special:FilePath/Paley9-unique-triangle.svg?width=300
dbo:wikiPageExternalLink	http://www.graphclasses.org/index.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 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
dbo:wikiPageWikiLink	dbr:Combinatorics dbr:Co-NP dbr:Robin_Thomas_(mathematician) dbr:Partially_ordered_set dbr:K-tree dbr:Vizing's_theorem dbr:Clique_(graph_theory) dbr:Trapezoid_graph dbr:Trivially_perfect_graph dbr:András_Hajnal dbr:Claude_Berge dbr:Maria_Chudnovsky dbr:Paul_Seymour_(mathematician) dbr:Intersection_graph dbr:Forbidden_graph_characterization dbr:Windmill_graph dbr:Graph_theory dbr:Tibor_Gallai dbr:Claw-free_graph dbr:Cograph dbr:Comparability_graph dbr:Longest_increasing_subsequence dbr:Graph_coloring dbr:Ellipsoid_method dbr:Tree_(graph_theory) dbr:Complement_graph dbr:Complete_bipartite_graph dbr:Mirsky's_theorem dbr:Lovász_number dbr:Induced_subgraph dbr:Trapezoid dbr:Annals_of_Mathematics dbr:Graph_(discrete_mathematics) dbr:Bipartite_graph dbr:Erdős–Szekeres_theorem dbr:Ptolemy's_inequality dbr:Treewidth dbr:Threshold_graph dbr:Wheel_graph dbr:Neil_Robertson_(mathematician) dbr:Linear_programming dbr:Strong_perfect_graph_theorem dbr:Interval_graph dbr:László_Lovász dbr:Kőnig's_theorem_(graph_theory) dbr:Dilworth's_theorem dbr:Perfect_graph_theorem dbr:Combinatorica dbr:Split_graph dbr:Ptolemaic_graph dbr:Edge_coloring dbr:Chordal_graph dbr:Induced_path dbr:American_Institute_of_Mathematics dbr:Strongly_chordal_graph dbc:Perfect_graphs dbr:Journal_of_Combinatorial_Theory dbr:Antichain dbr:Greedy_coloring dbr:Permutation_graph dbr:Block_graph dbr:Discrete_Mathematics_(journal) dbr:Distance-hereditary_graph dbr:Rook's_graph dbr:Line_graph dbr:Václav_Chvátal dbr:Polynomial_time dbr:Perfectly_orderable_graph dbr:Clique_number dbr:Maximum_independent_set_problem dbr:Maximum_matching dbr:Graph_coloring_problem dbr:Acta_Mathematica_Academiae_Scientiarum_Hungaricae dbr:Induced_cycle dbr:Maximum_clique_problem dbr:Semidefinite_program dbr:File:7-hole_and_antihole.svg dbr:File:Paley9-perfect.svg
dbp:wikiPageUsesTemplate	dbt:Good_article dbt:Math dbt:Mvar dbt:R dbt:Reflist dbt:Short_description
dct:subject	dbc:Perfect_graphs
gold:hypernym	dbr:Graph
rdfs:label	Perfect graph (en) Grafo perfecto (es) Perfekter Graph (de) Graphe parfait (fr) パーフェクトグラフ (ja) 완벽 그래프 (ko) Grafo perfetto (it) Grafo perfeito (pt) Perfecte graaf (nl) Graf doskonały (pl) Совершенный граф (ru) Досконалий граф (uk)
owl:sameAs	freebase:Perfect graph wikidata:Perfect graph dbpedia-de:Perfect graph dbpedia-es:Perfect graph dbpedia-it:Perfect graph dbpedia-nl:Perfect graph dbpedia-pl:Perfect graph dbpedia-fr:Perfect graph dbpedia-he:Perfect graph dbpedia-hu:Perfect graph dbpedia-ja:Perfect graph dbpedia-pt:Perfect graph dbpedia-ru:Perfect graph dbpedia-ko:Perfect graph yago-res:Perfect graph dbpedia-fa:Perfect graph dbpedia-sr:Perfect graph dbpedia-uk:Perfect graph dbpedia-global:Perfect graph
prov:wasDerivedFrom	wikipedia-en:Perfect_graph?oldid=1277540852&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Interval_graph.svg wiki-commons:Special:FilePath/7-hole_and_antihole.svg wiki-commons:Special:FilePath/Bipartite_line_graph.svg wiki-commons:Special:FilePath/Colored_split_graph.svg wiki-commons:Special:FilePath/Complementary_perfect_graphs.svg wiki-commons:Special:FilePath/Cubic_matchstick_graph.svg wiki-commons:Special:FilePath/Distance-hereditary_construction.svg wiki-commons:Special:FilePath/Line_perfect_graph.svg wiki-commons:Special:FilePath/Paley9-unique-triangle.svg wiki-commons:Special:FilePath/Permutation_graph.svg wiki-commons:Special:FilePath/Poset_et_graphe_de_comparabilité.svg
foaf:isPrimaryTopicOf	wikipedia-en:Perfect_graph
is dbo:wikiPageDisambiguates of	dbr:Perfect
is dbo:wikiPageRedirects of	dbr:Berge_graph dbr:Odd_antihole dbr:Odd_hole
is dbo:wikiPageWikiLink of	dbr:Circular-arc_graph dbr:Meyniel_graph dbr:Parity_graph dbr:Clique_(graph_theory) dbr:Martin_Charles_Golumbic dbr:Pathwidth dbr:Trapezoid_graph dbr:Trivially_perfect_graph dbr:Induced_matching dbr:Open-shop_scheduling dbr:Claude_Berge dbr:Maria_Chudnovsky dbr:Paul_Seymour_(mathematician) dbr:Forbidden_graph_characterization dbr:Clique_cover dbr:Dually_chordal_graph dbr:Fulkerson_Prize dbr:Graph_theory dbr:Property_testing dbr:Cycle_(graph_theory) dbr:Goldner–Harary_graph dbr:Perfect dbr:Claw-free_graph dbr:Cograph dbr:Comparability_graph dbr:Reconstruction_conjecture dbr:Skew_partition dbr:Graph_coloring dbr:Graph_property dbr:Complement_graph dbr:Polygon-circle_graph dbr:Lexicographic_product_of_graphs dbr:Mirsky's_theorem dbr:Lovász_number dbr:Polygon_covering dbr:Induced_subgraph dbr:Graph_(discrete_mathematics) dbr:Bipartite_graph dbr:Wheel_graph dbr:Glossary_of_graph_theory dbr:Neil_Robertson_(mathematician) dbr:148_(number) dbr:Folkman_graph dbr:Franklin_graph dbr:Herschel_graph dbr:Hoffman_graph dbr:Indifference_graph dbr:Möbius–Kantor_graph dbr:Matching_in_hypergraphs dbr:Strong_perfect_graph_theorem dbr:Helly_family dbr:Interval_graph dbr:Kőnig's_theorem_(graph_theory) dbr:Dilworth's_theorem dbr:Endre_Boros dbr:Neighbourhood_(graph_theory) dbr:Perfect_graph_theorem dbr:Split_graph dbr:Ptolemaic_graph dbr:Independent_set_(graph_theory) dbr:Chordal_graph dbr:Uniquely_colorable_graph dbr:Induced_path dbr:Line_perfect_graph dbr:List_of_conjectures dbr:Χ-bounded dbr:Greedy_coloring dbr:Permutation_graph dbr:Zero-divisor_graph dbr:Clique_problem dbr:Block_graph dbr:Discrete_Mathematics_(journal) dbr:Distance-hereditary_graph dbr:Rook's_graph dbr:List_of_graph_theory_topics dbr:Bruce_Reed_(mathematician) dbr:Line_graph dbr:Gérard_Cornuéjols dbr:Tolerance_graph dbr:Perfectly_orderable_graph dbr:Erdős–Hajnal_conjecture dbr:Kristina_Vušković dbr:Berge_graph dbr:Odd_antihole dbr:Odd_hole
is dbp:properties of	dbr:Goldner–Harary_graph dbr:Franklin_graph dbr:Hoffman_graph dbr:Möbius–Kantor_graph dbr:Rook's_graph
is foaf:primaryTopic of	wikipedia-en:Perfect_graph