About: Perfect graph

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia-live.demo.openlinksw.com

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.cs.concordia.ca/~chvatal/perfect/problems.html http://www.graphclasses.org/classes/gc_56.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/index.html https://web.archive.org/web/20100522154759/http:/www.elsevier.com/wps/find/bookdescription.cws_home/699916/description%23description http://www.elsevier.com/wps/find/bookdescription.cws_home/699916/description%23description
dbo:wikiPageWikiLink	dbr:Perfectly_orderable_graph dbr:Tree_(graph_theory) dbr:Wheel_graph dbr:Clique_(graph_theory) dbr:Clique_number dbr:Ptolemy's_inequality dbr:Edge_coloring dbr:Perfect_graph_theorem dbr:Longest_increasing_subsequence dbr:Rook's_graph dbr:Ellipsoid_method dbr:Antichain dbr:Linear_programming dbr:András_Hajnal dbr:Paul_Seymour_(mathematician) dbr:Maximum_independent_set_problem dbr:Forbidden_graph_characterization dbr:Claw-free_graph dbr:K-tree dbr:Combinatorics dbr:Complement_graph dbr:Kőnig's_theorem_(graph_theory) dbr:Split_graph dbr:Claude_Berge dbc:Perfect_graphs dbr:Chordal_graph dbr:Co-NP dbr:Interval_graph dbr:Greedy_coloring dbr:Graph_theory dbr:Annals_of_Mathematics dbr:Bipartite_graph dbr:Graph_coloring dbr:Maria_Chudnovsky dbr:Cograph dbr:Induced_subgraph dbr:Ptolemaic_graph dbr:László_Lovász dbr:Trapezoid dbr:Complete_bipartite_graph dbr:Václav_Chvátal dbr:Neil_Robertson_(mathematician) dbr:Trapezoid_graph dbr:American_Institute_of_Mathematics dbr:Partially_ordered_set dbr:Intersection_graph dbr:Journal_of_Combinatorial_Theory dbr:Discrete_Mathematics_(journal) dbr:Distance-hereditary_graph dbr:Strongly_chordal_graph dbr:Line_graph dbr:Dilworth's_theorem dbr:Robin_Thomas_(mathematician) dbr:Vizing's_theorem dbr:Treewidth dbr:Mirsky's_theorem dbr:Graph_(discrete_mathematics) dbr:Threshold_graph dbr:Erdős–Szekeres_theorem dbr:Tibor_Gallai dbr:Combinatorica dbr:Comparability_graph dbr:Permutation_graph dbr:Trivially_perfect_graph dbr:Block_graph dbr:Lovász_number dbr:Windmill_graph dbr:Acta_Mathematica_Academiae_Scientiarum_Hungaricae dbr:Strong_perfect_graph_theorem dbr:Polynomial_time dbr:Induced_path dbr:Graph_coloring_problem dbr:Maximum_clique_problem dbr:Maximum_matching dbr:Induced_cycle dbr:Semidefinite_program dbr:File:7-hole_and_antihole.svg dbr:File:Paley9-perfect.svg
dbp:wikiPageUsesTemplate	dbt:Good_article dbt:Reflist dbt:Math dbt:R dbt:Mvar 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) Grafo perfetto (it) 완벽 그래프 (ko) Perfecte graaf (nl) Grafo perfeito (pt) Graf doskonały (pl) Совершенный граф (ru) Досконалий граф (uk)
owl:sameAs	freebase:Perfect graph yago-res:Perfect graph wikidata:Perfect graph dbpedia-it:Perfect graph dbpedia-nl:Perfect graph dbpedia-de:Perfect graph dbpedia-fr:Perfect graph dbpedia-ja:Perfect graph dbpedia-pt:Perfect graph dbpedia-he:Perfect graph dbpedia-es:Perfect graph dbpedia-hu:Perfect graph dbpedia-fa:Perfect graph dbpedia-ru:Perfect graph dbpedia-pl:Perfect graph dbpedia-ko:Perfect graph dbpedia-sr:Perfect graph dbpedia-uk:Perfect graph dbpedia-global:Perfect graph dbr:Perfect graph
prov:wasDerivedFrom	wikipedia-en:Perfect_graph?oldid=1277540852&ns=0
foaf:depiction	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 wiki-commons:Special:FilePath/Interval_graph.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:Gérard_Cornuéjols dbr:Perfectly_orderable_graph dbr:Glossary_of_graph_theory dbr:Graph_property dbr:Wheel_graph dbr:Clique_(graph_theory) dbr:Cycle_(graph_theory) dbr:Perfect_graph_theorem dbr:Rook's_graph dbr:Neighbourhood_(graph_theory) dbr:Paul_Seymour_(mathematician) dbr:Independent_set_(graph_theory) dbr:Clique_cover dbr:Forbidden_graph_characterization dbr:Claw-free_graph dbr:Pathwidth dbr:Perfect dbr:Complement_graph dbr:Kőnig's_theorem_(graph_theory) dbr:Split_graph dbr:Endre_Boros dbr:Claude_Berge dbr:Chordal_graph dbr:Interval_graph dbr:Clique_problem dbr:Bruce_Reed_(mathematician) dbr:Greedy_coloring dbr:Graph_theory dbr:Bipartite_graph dbr:Graph_coloring dbr:Maria_Chudnovsky dbr:Fulkerson_Prize dbr:List_of_conjectures dbr:Martin_Charles_Golumbic dbr:Cograph dbr:Lexicographic_product_of_graphs dbr:Induced_subgraph dbr:Ptolemaic_graph dbr:Property_testing dbr:Neil_Robertson_(mathematician) dbr:Folkman_graph dbr:Franklin_graph dbr:Goldner–Harary_graph dbr:Herschel_graph dbr:Hoffman_graph dbr:Indifference_graph dbr:Möbius–Kantor_graph dbr:Polygon-circle_graph dbr:Trapezoid_graph dbr:Uniquely_colorable_graph dbr:Helly_family dbr:Discrete_Mathematics_(journal) dbr:Distance-hereditary_graph dbr:List_of_graph_theory_topics dbr:148_(number) dbr:Line_graph dbr:Dilworth's_theorem dbr:Mirsky's_theorem dbr:Open-shop_scheduling dbr:Graph_(discrete_mathematics) dbr:Circular-arc_graph dbr:Comparability_graph dbr:Permutation_graph dbr:Skew_partition dbr:Trivially_perfect_graph dbr:Block_graph dbr:Lovász_number dbr:Reconstruction_conjecture dbr:Dually_chordal_graph dbr:Χ-bounded dbr:Polygon_covering dbr:Erdős–Hajnal_conjecture dbr:Meyniel_graph dbr:Parity_graph dbr:Line_perfect_graph dbr:Matching_in_hypergraphs dbr:Strong_perfect_graph_theorem dbr:Tolerance_graph dbr:Zero-divisor_graph dbr:Kristina_Vušković dbr:Induced_path dbr:Induced_matching dbr:Berge_graph dbr:Odd_antihole dbr:Odd_hole
is dbp:properties of	dbr:Rook's_graph dbr:Franklin_graph dbr:Goldner–Harary_graph dbr:Hoffman_graph dbr:Möbius–Kantor_graph
is foaf:primaryTopic of	wikipedia-en:Perfect_graph