Chordal Graph

A chordal graph is a simple graph in which every graph cycle of length four and greater has a cycle chord. In other words, a chordal graph is a graph possessing no chordless cycles of length four or greater (cf. West 2000, p. 225; Gross and Yellen 2006, p. 437).

The numbers of simple chordal graphs on , 2, ... nodes are 1, 2, 4, 10, 27, 94, 393, ... (OEIS A048193). The first few are illustrated above, though many are trivially chordal since they possess no cycles of length .

The corresponding numbers of simple connected chordal graphs are 1, 1, 2, 5, 15, 58, 272, ... (OEIS A048192). The first few are illustrated above, though many are again chordal only trivially.

A split graph is a chordal graph whose graph complement is also chordal (Royle 2000).

Every chordal graph is perfect.

It is possible to recognize chordal graphs in linear time. Furthermore, a maximum clique of a chordal graph can be found in polynomial time although the problem is NP-complete for general graphs.

A chordal graph (which possesses no chordless cycles) is not the same as (or converse of) a chordless graph (which possesses no chords). For example, the square graph  is chordless but not chordal, the diamond graph and tetrahedral graph  are chordal but not chordless, and empty graphs , path graphs , and the triangle graph  are both chordal and chordless.

REFERENCES

Blair, J. R. S. and Peyton, B. W. "An Introduction to Chordal Graphs and Clique Trees." In Graph Theory and Sparse Matrix Computation (Ed. A. George, J. R. Gilbert, and J. W. H. Liu). New York: Springer-Verlag, pp.1-29, 1993.

Brandstadt, A.; Le, V. B.; and Spinrad, J. P. Graph Classes: A Survey. Philadelphia, PA: SIAM, 1999.

 Bulatov, Y. "Mathematica Bits: Chordal Graph Package Update." http://mathematica-bits.blogspot.com/2011/02/chordal-graph-usage.html.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.Habib, M.; McConnell, R.; Paul, C.; and Viennot, L. "Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition, and Consecutive Ones Testing." Theoret. Comput. Sci. 234, 59-84, 2000.

Rose, D.; Lueker, G.; and Tarjan, R. E. "Algorithmic Aspects of Vertex Elimination on Graphs." SIAM J. Comput. 5, 266-283, 1976.

Royle, G. F. "Counting Set Covers and Split Graphs." J. Integer Seq. 3, Article 00.2.6, 2000.

 https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html.Sloane, N. J. A. Sequences A048192 and A048193 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. "Chordal Graphs" and "Chordal Graphs Revisited." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 224-226 and 323-328, 2000.