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

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 .

Property Value
dbo:abstract
• 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. (en)
dbo:thumbnail
dbo:wikiPageID
• 670531 (xsd:integer)
dbo:wikiPageLength
• 16620 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
• 1039640450 (xsd:integer)
dbp:wikiPageUsesTemplate
dct:subject
gold:hypernym
rdf:type
rdfs:comment
• 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 . (en)
rdfs:label
• Perfect graph (en)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of