Elsevier

Discrete Mathematics

Volume 16, Issue 4, December 1976, Pages 361-381
Discrete Mathematics

Characterization problems for graphs, partially ordered sets, lattices, and families of sets

https://doi.org/10.1016/S0012-365X(76)80011-8Get rights and content
Under an Elsevier user license
open archive

A standard problem in combinatorial theory is to characterize structures which satisfy a certain property by providing a minimum list of forbidden substructures, for example, Kuratowski's well known characterization of planar graphs. In this paper, we establish connections between characterization problems for interval graphs, circular are graphs, comparability graphs, planar lattices, 0–1 matrices, interval orders, partially ordered sets with dimension at most two, partially ordered sets with interval dimension at most two, and related problems involving the representation of families of finite sets by points or intervals of the real line. We use these connections to determine the collection of all 3-irreducible posets. We are then able to determine the collection of all 3-interval irreducible posets of height one and the set of all forbidden subgraphs with clique covering number two in the characterization of circular are graphs.

Cited by (0)