A chordal graph is a finite 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. Harary and Palmer 1973, p. 264; West
2000, p. 225; Gross and Yellen 2006, p. 437). Harary and Palmer (1973,
p. 264) call such a graph a rigid circuit graph.
The numbers of nonisomorphicsimple chordal graphs on ,
2, ... vertices 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 nonisomorphicsimpleconnected 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.
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." https://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.Harary,
F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems."
In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam,
Netherlands: North-Holland, pp. 259-275, 1973.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, ... vertices 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 
.
and positive integer 
, the decision problem of whether 
has a clique
of size at least 
is NP-complete.
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."