## On hereditary subdirectly irreducible graphs.(English)Zbl 0567.05045

Let $${\mathcal C}$$ be a class of loopless directed graphs closed under the categorical product (conjunction) $$\Pi$$ and under taking induced subgraphs. A graph $$G\in {\mathcal C}$$ is $${\mathcal C}$$-subdirectly irreducible if it satisfies the following condition: whenever G is isomorphic to an induced subgraph G’ of $$\prod_{i\in I}H_ i$$ with each $$H_ i\in {\mathcal C}$$ (i$$\in I)$$ such that $$p_ i(G')=H_ i$$ for all projections $$p_ i$$, $$i\in I$$, there exists a $$j\in I$$ such that the restriction of $$p_ j$$ to G’ is an isomorphism onto $$H_ j$$. This paper contains a description of all classes $${\mathcal C}$$ of graphs for which the property of $${\mathcal C}$$-subdirect irreducibility is hereditary, i.e., for which the class of $${\mathcal C}$$-subdirectly irreducible graphs is closed under taking induced subgraphs. A similar description for loopless undirected graphs was given earlier by the same author (Abstracta Eight Winter School on Abstract Analysis, Praha 1980, 180-193; cf. also Rep. ZW 193/83, Math. Centrum Amsterdam 1983). Subdirectly irreducible graphs were also studied by B. Fawcett (Ph.D. thesis, McMaster Univ. 1060), G. Sabidussi [Infinite finite sets, Colloq. Honour Paul Erdős, Keszthely 1973, Colloq. Math. Soc. János Bolyai 10, 1199-1226 (1975; Zbl 0308.05124)] and the reviewer [ibid., 857-866 (1975; Zbl 0308.05125)].
Reviewer: P.Hell

### MSC:

 05C99 Graph theory

### Citations:

Zbl 0308.05124; Zbl 0308.05125
Full Text: