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

✍ Scribed by William T. Trotter Jr.; John I. Moore Jr.

• Publisher: Elsevier Science
• Year: 1976
• Tongue: English
• Weight: 909 KB
• Volume: 16
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(76)80011-8

✦ Synopsis

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 arc 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 arc graphs.