TOPICS
Search

Berge Graph


A Berge graph is a simple graph that contains no odd graph hole and no odd graph antihole. The strong perfect graph theorem asserts that a graph is perfect iff it is a Berge graph.


See also

Chordal Graph, Graph Antihole, Graph Hole, Perfect Graph, Strong Perfect Graph Theorem

Explore with Wolfram|Alpha

References

Cornuéjols, G. "The Strong Perfect Graph Conjecture." International Congress of Mathematics, Beijing, China, 2002, Vol. 3. pp. 547-559. http://integer.gsia.cmu.edu/webpub/SPGCsurvey.pdf.Chvátal, V. "The Strong Perfect Graph Theorem." http://www.cs.concordia.ca/~chvatal/perfect/spgt.html.

Referenced on Wolfram|Alpha

Berge Graph

Cite this as:

Weisstein, Eric W. "Berge Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BergeGraph.html

Subject classifications