Perfect graph
- Triangulated graphs
- Bipartite graphs
- Complete graph
- Co - graph
- Vergleichbarkeitsgraphen
In graph theory, a graph is called perfect if for every induced subgraph that its clique number coincides with its chromatic number. An induced subgraph of a graph consists of a subset of the nodes and all incident edges.
In a perfect graph chromatic number, clique number and stability number can be computed in polynomial time, the calculation of general graphs is NP -complete. It can be determined in polynomial time whether a graph is perfect. Examples of perfect graphs are bipartite graphs, line graphs of bipartite graphs and their complements. They form the basis for the strong perfect graph theorem and therefore in this context as simple perfect graphs (english basic) respectively. Other examples of perfect graphs are triangulated graphs and chordal bipartite graphs.
According to the theorem on perfect graphs, the following are equivalent:
The second characteristic is known as a weak perfect graph theorem was proved in 1972 by László Lovász and is therefore now set called Lovász. The third characteristic is also known as a strong theorem on perfect graphs, and has been proved only in May 2002. Both statements were ( was at a conference in Halle- Wittenberg published his conjecture in 1963 ) in 1960 by Claude mountains positioned than conjecture.