TOPICS
Search

Chordless Graph


A chordless graph is a simple graph possessing no chords.

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 C_4 is chordless but not chordal, the diamond graph and tetrahedral graph K_4 are chordal but not chordless, and empty graphs K^__n, path graphs P_n, and the triangle graph C_3 are both chordal and chordless.

A biconnected graph is chordless iff it is minimally 2-connected, meaning that deletion of any edge makes it no longer biconnected (Dirac 1967, Plummer 1968).

Aboulker et al. (2012) showed that every chordless graph on at least two vertices has at least two vertices of degree at most 2. Since every subgraph of a chordless graph is chordless, the graph degeneracy of a chordless graph is therefore at most 2. Equivalently, the 3-core of every chordless graph is empty. The converse is false: the diamond graph has degeneracy 2 and hence an empty 3-core, but is not chordless.

ChordlessConnected

The numbers of connected simple chordless graphs on n=1, 2, ... nodes are 1, 1, 2, 4, 10, 27, ... (OEIS A287693), the first few of which are illustrated above.

Chordless

The numbers of not-necessarily connected simple chordless graphs on n=1, 2, ... nodes are 1, 2, 4, 9, 21, 56, ... (OEIS A287694), the first few of which are illustrated above.


See also

Biconnected Graph, Chordal Graph, Chordless Cycle, Cycle Chord, Graph Degeneracy, k-Core

Explore with Wolfram|Alpha

References

Aboulker, P.; Radovanović, M.; Trotignon, N.; and Vušković, K. "Graphs That Do Not Contain a Cycle with a Node That Has at Least Two Neighbors on It." SIAM J. Disc. Math. 26, 1510-1531, 2012. https://doi.org/10.1137/11084933X.Dirac, G. A. "Minimally 2-Connected Graphs." J. reine angew. Math. 228, 204-216, 1967. https://doi.org/10.1515/crll.1967.228.204.Plummer, M. D. "On Minimal Blocks." Trans. Amer. Math. Soc. 134, 85-94, 1968. https://doi.org/10.1090/S0002-9947-1968-0228369-8.Sloane, N. J. A. Sequences A287693 and A287694 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Chordless Graph

Cite this as:

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

Subject classifications