Abstract: In the upper bound graph of a poset P,
the vertex set is and xy
is an edge if there exists an element with We obtain some properties of a
minimal upper bound graph H which
contains a given graph G as an induced
subgraph. According to these properties, we consider forbidden subgraph
characterizations on some kinds of families of upper bound graphs, that is,
split upper bound graphs, threshold upper bound graphs, etc.
Keywords and phrases: upper bound graph, forbidden subgraph.
