Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Perfect_graph> ?p ?o. }
Showing items 1 to 45 of
45
with 100 items per page.
- 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. 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.".
- Perfect_graph thumbnail Paley9-perfect.svg?width=300.
- Perfect_graph wikiPageExternalLink p02.xhtml.
- Perfect_graph wikiPageExternalLink perfectgraph.
- Perfect_graph wikiPageExternalLink problems.html.
- Perfect_graph wikiPageExternalLink spgt.html.
- Perfect_graph wikiPageExternalLink description.
- Perfect_graph wikiPageExternalLink gc_56.html.
- Perfect_graph wikiPageExternalLink index.html.
- Perfect_graph wikiPageID "670531".
- Perfect_graph wikiPageRevisionID "581216256".
- Perfect_graph hasPhotoCollection Perfect_graph.
- Perfect_graph subject Category:Perfect_graphs.
- Perfect_graph type Abstraction100002137.
- Perfect_graph type Communication100033020.
- Perfect_graph type Graph107000195.
- Perfect_graph type PerfectGraphs.
- Perfect_graph type VisualCommunication106873252.
- Perfect_graph comment "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.".
- Perfect_graph label "Graf doskonały".
- Perfect_graph label "Grafo perfecto".
- Perfect_graph label "Grafo perfeito".
- Perfect_graph label "Grafo perfetto".
- Perfect_graph label "Graphe parfait".
- Perfect_graph label "Perfect graph".
- Perfect_graph label "Perfecte graaf".
- Perfect_graph label "Perfekter Graph".
- Perfect_graph label "Совершенный граф".
- Perfect_graph label "パーフェクトグラフ".
- Perfect_graph sameAs Perfekter_Graph.
- Perfect_graph sameAs Grafo_perfecto.
- Perfect_graph sameAs Graphe_parfait.
- Perfect_graph sameAs Grafo_perfetto.
- Perfect_graph sameAs パーフェクトグラフ.
- Perfect_graph sameAs 완벽_그래프.
- Perfect_graph sameAs Perfecte_graaf.
- Perfect_graph sameAs Graf_doskonały.
- Perfect_graph sameAs Grafo_perfeito.
- Perfect_graph sameAs m.031hx5.
- Perfect_graph sameAs Q1187620.
- Perfect_graph sameAs Q1187620.
- Perfect_graph sameAs Perfect_graph.
- Perfect_graph wasDerivedFrom Perfect_graph?oldid=581216256.
- Perfect_graph depiction Paley9-perfect.svg.
- Perfect_graph isPrimaryTopicOf Perfect_graph.
