Perfect Graph
Saturday, 20. September 2008, 18:39:56
1. Definition
---Wikipedia
2. Chordal graphs are subset of perfect graphs. They are sometimes also called triangulated graphs.
---Wikipedia
3. Check class notes at U. Waterloo on chordal graphs and recognizing chordal graphs.
4. Professor David Eppstein at UC Irvin gave python implementation of one chordal graph recognization algorithm proposed in the paper "Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition and Consecutive Ones".
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the clique number of that subgraph. That is, if every complete subgraph has at most k vertices, the graph can be colored with k colors, and this same relation between complete subgraphs and coloring holds in every induced subgraph of the graph.
---Wikipedia
2. Chordal graphs are subset of perfect graphs. They are sometimes also called triangulated graphs.
A graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle.
---Wikipedia
3. Check class notes at U. Waterloo on chordal graphs and recognizing chordal graphs.
4. Professor David Eppstein at UC Irvin gave python implementation of one chordal graph recognization algorithm proposed in the paper "Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition and Consecutive Ones".
WIDGETIZE