is_chordal¶

Checks whether G is a chordal graph.

A graph is chordal if every cycle of length at least 4 has a chord (an edge joining two nodes not adjacent in the cycle).

Parameters

Ggraph: A NetworkX graph.

Returns

chordalbool: True if G is a chordal graph and False otherwise.

Raises

NetworkXNotImplemented: The algorithm does not support DiGraph, MultiGraph and MultiDiGraph.

Notes

The routine tries to go through every node following maximum cardinality search. It returns False when it finds that the separator for any node is not a clique. Based on the algorithms in [1].

References

1: R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984), pp. 566–579.

Examples

>>> e = [
...     (1, 2),
...     (1, 3),
...     (2, 3),
...     (2, 4),
...     (3, 4),
...     (3, 5),
...     (3, 6),
...     (4, 5),
...     (4, 6),
...     (5, 6),
... ]
>>> G = nx.Graph(e)
>>> nx.is_chordal(G)
True