Perfect graph theorem
id:
perfect-graph-theorem-165-8429482
title:
Perfect graph theorem
text:
In graph theory, the perfect graph theorem of László Lovász (1972a, 1972b) states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge (1961, 1963), and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.
brand slug:
wiki
category slug:
encyclopedia
description:
An undirected graph is perfect if and only if its complement graph is also perfect
original url:
https://en.wikipedia.org/wiki/Perfect_graph_theorem
date created:
2004-05-21T22:03:08Z
date modified:
2024-08-29T20:27:12Z
main entity:
{"identifier":"Q2800071","url":"https://www.wikidata.org/entity/Q2800071"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/c/cf/Complementary_perfect_graphs.svg","width":1026,"height":432}
fields total:
13
integrity:
16