zbMATH — the first resource for mathematics

Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. (English) Zbl 0776.06002
The 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\).

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
Full Text: DOI
[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.