Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures.

*(English)*Zbl 0776.06002The paper characterizes the critically indecomposable binary relational structures showing that for every odd order \((\geq 5)\) there are five and for every even order \((\geq 6)\) there are four of them (up to a certain type of equivalence). The classes of critically indecomposable posets, graphs, tournaments and digraphs are included as special cases. It is also shown that every indecomposable structure of order \(n+2\) \((n\geq 5)\) has an indecomposable substructure of order \(n\).

Reviewer: P.L.Erdös (Almare)

##### MSC:

06A06 | Partial orders, general |

05C99 | Graph theory |

05C75 | Structural characterization of families of graphs |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

05C20 | Directed graphs (digraphs), tournaments |

##### Keywords:

finite poset; lexicographic product; embeddings; critically indecomposable binary relational structures; critically indecomposable posets; graphs; tournaments; digraphs
PDF
BibTeX
XML
Cite

\textit{J. H. Schmerl} and \textit{W. T. Trotter}, Discrete Math. 113, No. 1--3, 191--205 (1993; Zbl 0776.06002)

Full Text:
DOI

**OpenURL**

##### References:

[1] | D. Kelly, Comparability graphs, in: I. Rival, ed., Graphs and Order (Reidel, Dordrecht) 3-40. · Zbl 0573.05055 |

[2] | Schmerl, J.H., Arborescent structures, II: interpretability in the theory of trees, Trans. amer. math. soc., 266, 629-643, (1981) · Zbl 0475.03014 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.