On hereditary subdirectly irreducible graphs. (English) Zbl 0567.05045

Vinárek, J.

Acta Univ. Carol., Math. Phys. 25, No. 2, 3-10 (1984).

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

Keywords:

categorical product; conjunction; Subdirectly irreducible graphs

Citations:

Zbl 0308.05124; Zbl 0308.05125