Premium
On the structure of hereditary classes of graphs
Author(s) -
Scheinerman Edward R.
Publication year - 1986
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.3190100414
Subject(s) - mathematics , combinatorics , cograph , disjoint sets , discrete mathematics , indifference graph , disjoint union (topology) , chordal graph , graph , 1 planar graph
Abstract A class of graphs is hereditary if it is closed under taking induced subgraphs. Classes associated with graph representations have “composition sequences” and we show that this concept is equivalent to a notion of “amalgamation” which generalizes disjoint union of graphs. We also discuss how general hereditary classes of graphs are built up from representation classes.