Containment Graphs, Posets, and Related Classes of Graphs

MaRDI QIDQ3972134zbMATH OpenFDO

Authors Martin Charles Golumbic, Edward Scheinerman

Publication date 25 June 1992

Full work available at URL https://arxiv.org/abs/1907.07414

zbMATH Keywords

containment graphcontainment posetcontainment representations

Mathematics Subject Classification ID

Partial orders, general (06A06) Structural characterization of families of graphs (05C75)

Abstract: In this paper, we introduce the notion of the containment graph of a family of sets and containment classes of graphs and posets. Let $Z$ be a family of nonempty sets. We call a (simple, finite) graph G = (V, E) a $Z$-containment graph provided one can assign to each vertex $v_{i}inV$ a set $S_{i}inZ$ such that $v_i{v}_{j}inE$ if and only if $S_{i}subset{S}_j$ or $S_{j}subset{S}_i$ . Similarly, we call a (strict) partially ordered set $P=(V,<)$ a $Z$-containment poset if to each $v_{i}inV$ we can assign a set $S_{i}inZ$ such that $v_i<v_j$ if and only if $S_{i}subset{S}_j$. Obviously, $G$ is the comparability graph of $P$. We give some basic results on containment graphs and investigate the containment graphs of iso-oriented boxes in $d$-space. We present a characterization of those classes of posets and graphs that have containment representations by sets of a specific type, and we extend our results to ``injective containment classes. After that we discuss similar characterizations for intersection, overlap, and disjointedness classes of graphs. Finally, in the last section we discuss the nonexistence of a characterization theorem for ``strong containment classes of graphs.

Recommendations

• The poset of graphs ordered by induced containment
• scientific article; zbMATH DE number 5949787
• Posets and planar graphs
• scientific article; zbMATH DE number 1890838
• Cover-incomparability graphs of posets
• Containment graphs and posets of paths in a tree: wheels and partial wheels
• scientific article; zbMATH DE number 7157680
• scientific article; zbMATH DE number 568841
• Poset boxicity of graphs
• Posets and VPG graphs

Cited in

(25)

• scientific article; zbMATH DE number 15259 (Why is no real title available?)
• On circle containment orders
• scientific article; zbMATH DE number 1890838 (Why is no real title available?)
• Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
• Recent results on containment graphs of paths in a tree
• Min-orderable digraphs
• Degrees of freedom versus dimension for containment orders
• Maximum independent set and maximum clique algorithms for overlap graphs
• Incidence posets and cover graphs
• Spherical containment and the Minkowski dimension of partial orders
• On \(k\)-tree containment graphs of paths in a tree
• On the structure of hereditary classes of graphs
• On containment graphs of paths in a tree
• Containment graphs and posets of paths in a tree: wheels and partial wheels
• Dimension of CPT posets
• Permutation bigraphs and interval containments
• Inclusion transformations: \((n,m)\)-graphs and their classification
• Subtree filament graphs are subtree overlap graphs
• End vertices in containment interval graphs
• Containment orders – a lifelong journey
• Algorithmic aspects of intersection graphs and representation hypergraphs
• Containment orders for similar ellipses with a common center
• On dually-CPT and strongly-CPT posets
• scientific article; zbMATH DE number 5949787 (Why is no real title available?)
• Representing digraphs using intervals or circular arcs

This page was built for publication: Containment Graphs, Posets, and Related Classes of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972134)