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.
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.
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.
, 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 
.
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.
Bulatov, Y. "Mathematica Bits:
Chordal Graph Package Update."