Premium
A generalization of chordal graphs
Author(s) -
Seymour P. D.,
Weaver R. W.
Publication year - 1984
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190080206
Subject(s) - chordal graph , combinatorics , mathematics , generalization , conjecture , planar graph , clique , discrete mathematics , simple (philosophy) , clique sum , triangulation , 1 planar graph , graph , geometry , mathematical analysis , philosophy , epistemology
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.