Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Perfect_graph> ?p ?o }
- Perfect_graph abstract "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. Due to the strong perfect graph theorem, 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.".
- Perfect_graph thumbnail Paley9-perfect.svg?width=300.
- Perfect_graph wikiPageExternalLink description.
- Perfect_graph wikiPageExternalLink p02.xhtml.
- Perfect_graph wikiPageExternalLink perfectgraph.
- Perfect_graph wikiPageExternalLink problems.html.
- Perfect_graph wikiPageExternalLink spgt.html.
- Perfect_graph wikiPageExternalLink gc_56.html.
- Perfect_graph wikiPageExternalLink index.html.
- Perfect_graph wikiPageID "670531".
- Perfect_graph wikiPageLength "13983".
- Perfect_graph wikiPageOutDegree "91".
- Perfect_graph wikiPageRevisionID "683711184".
- Perfect_graph wikiPageWikiLink American_Institute_of_Mathematics.
- Perfect_graph wikiPageWikiLink Annals_of_Mathematics.
- Perfect_graph wikiPageWikiLink Antichain.
- Perfect_graph wikiPageWikiLink Bipartite_graph.
- Perfect_graph wikiPageWikiLink Block_graph.
- Perfect_graph wikiPageWikiLink Category:Perfect_graphs.
- Perfect_graph wikiPageWikiLink Chordal_graph.
- Perfect_graph wikiPageWikiLink Claude_Berge.
- Perfect_graph wikiPageWikiLink Claw-free_graph.
- Perfect_graph wikiPageWikiLink Clique_(graph_theory).
- Perfect_graph wikiPageWikiLink Clique_problem.
- Perfect_graph wikiPageWikiLink Co-NP.
- Perfect_graph wikiPageWikiLink Cograph.
- Perfect_graph wikiPageWikiLink Combinatorics.
- Perfect_graph wikiPageWikiLink Comparability_graph.
- Perfect_graph wikiPageWikiLink Complement_graph.
- Perfect_graph wikiPageWikiLink Complete_bipartite_graph.
- Perfect_graph wikiPageWikiLink Dilworths_theorem.
- Perfect_graph wikiPageWikiLink Discrete_Mathematics_(journal).
- Perfect_graph wikiPageWikiLink Distance-hereditary_graph.
- Perfect_graph wikiPageWikiLink Edge_coloring.
- Perfect_graph wikiPageWikiLink Ellipsoid_method.
- Perfect_graph wikiPageWikiLink Erdős–Szekeres_theorem.
- Perfect_graph wikiPageWikiLink Forbidden_graph_characterization.
- Perfect_graph wikiPageWikiLink Glossary_of_graph_theory.
- Perfect_graph wikiPageWikiLink Graph_(mathematics).
- Perfect_graph wikiPageWikiLink Graph_coloring.
- Perfect_graph wikiPageWikiLink Graph_coloring_problem.
- Perfect_graph wikiPageWikiLink Graph_theory.
- Perfect_graph wikiPageWikiLink Greedy_coloring.
- Perfect_graph wikiPageWikiLink Gérard_Cornuéjols.
- Perfect_graph wikiPageWikiLink Independent_set_(graph_theory).
- Perfect_graph wikiPageWikiLink Induced_cycle.
- Perfect_graph wikiPageWikiLink Induced_path.
- Perfect_graph wikiPageWikiLink Induced_subgraph.
- Perfect_graph wikiPageWikiLink Intersection_graph.
- Perfect_graph wikiPageWikiLink Interval_graph.
- Perfect_graph wikiPageWikiLink K-tree.
- Perfect_graph wikiPageWikiLink Kxc3xb6nigs_theorem_(graph_theory).
- Perfect_graph wikiPageWikiLink Line_graph.
- Perfect_graph wikiPageWikiLink Linear_programming.
- Perfect_graph wikiPageWikiLink Longest_increasing_subsequence.
- Perfect_graph wikiPageWikiLink László_Lovász.
- Perfect_graph wikiPageWikiLink Maria_Chudnovsky.
- Perfect_graph wikiPageWikiLink Matching_(graph_theory).
- Perfect_graph wikiPageWikiLink Maximum_clique_problem.
- Perfect_graph wikiPageWikiLink Maximum_independent_set_problem.
- Perfect_graph wikiPageWikiLink Maximum_matching.
- Perfect_graph wikiPageWikiLink Mirskys_theorem.
- Perfect_graph wikiPageWikiLink Neil_Robertson_(mathematician).
- Perfect_graph wikiPageWikiLink Partially_ordered_set.
- Perfect_graph wikiPageWikiLink Paul_Seymour_(mathematician).
- Perfect_graph wikiPageWikiLink Perfect_graph_theorem.
- Perfect_graph wikiPageWikiLink Perfectly_orderable_graph.
- Perfect_graph wikiPageWikiLink Permutation_graph.
- Perfect_graph wikiPageWikiLink Polynomial_time.
- Perfect_graph wikiPageWikiLink Robin_Thomas_(mathematician).
- Perfect_graph wikiPageWikiLink Rooks_graph.
- Perfect_graph wikiPageWikiLink Split_graph.
- Perfect_graph wikiPageWikiLink Strong_perfect_graph_theorem.
- Perfect_graph wikiPageWikiLink Strongly_chordal_graph.
- Perfect_graph wikiPageWikiLink Threshold_graph.
- Perfect_graph wikiPageWikiLink Tibor_Gallai.
- Perfect_graph wikiPageWikiLink Time_complexity.
- Perfect_graph wikiPageWikiLink Trapezoid.
- Perfect_graph wikiPageWikiLink Trapezoid_graph.
- Perfect_graph wikiPageWikiLink Tree_(graph_theory).
- Perfect_graph wikiPageWikiLink Treewidth.
- Perfect_graph wikiPageWikiLink Trivially_perfect_graph.
- Perfect_graph wikiPageWikiLink Vizings_theorem.
- Perfect_graph wikiPageWikiLink Václav_Chvátal.
- Perfect_graph wikiPageWikiLink Wheel_graph.
- Perfect_graph wikiPageWikiLink Windmill_graph.
- Perfect_graph wikiPageWikiLink File:7-hole_and_antihole.svg.
- Perfect_graph wikiPageWikiLink File:Paley9-perfect.svg.
- Perfect_graph wikiPageWikiLinkText "Perfect graph".
- Perfect_graph wikiPageWikiLinkText "Perfect".
- Perfect_graph wikiPageWikiLinkText "perfect graph conjecture".
- Perfect_graph wikiPageWikiLinkText "perfect graph".
- Perfect_graph wikiPageWikiLinkText "perfect".
- Perfect_graph wikiPageWikiLinkText "perfection".
- Perfect_graph wikiPageWikiLinkText "perfectness".
- Perfect_graph wikiPageWikiLinkText "strong perfect graph conjecture".
- Perfect_graph hasPhotoCollection Perfect_graph.
- Perfect_graph wikiPageUsesTemplate Template:Cite_conference.
- Perfect_graph wikiPageUsesTemplate Template:Cite_document.
- Perfect_graph wikiPageUsesTemplate Template:Cite_journal.