A generalization of chordal graphs

P. D. Seymour, R. W. Weaver

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

In a 3‐connected planar triangulation, every circuit of length ≥ 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are “separated” by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In this paper we prove his conjecture, that if G is simple and 3‐connected and every circuit of length ≥ 4 has at least two “bridges,” then G may be built up by “clique‐sums” starting from complete graphs and planar triangulations. This is a generalization of Dirac's theorem about chordal graphs.

Original languageEnglish (US)
Pages (from-to)241-251
Number of pages11
JournalJournal of Graph Theory
Volume8
Issue number2
DOIs
StatePublished - 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'A generalization of chordal graphs'. Together they form a unique fingerprint.

Cite this