History

Please fill in your query. A complete syntax description you will find on the General Help page.
Subdirect decomposition of $n$-chromatic graphs. (English)
J. Algebr. Comb. 8, No.2, 157-168 (1998).
It is shown that any $n$-chromatic graph is a full subdirect product of copies of $K_{n}$ and $K_{n+1}$, with the exception of some particular graphs which are full subdirect products of copies of $A_{n}$ and $A_{n+1}$, where $A_{n}=K_{n+1}-K_{2}$; full means here that the projections of the decomposition are epimorphic in edges. This improves G. Sabidussi’s results in [Infinite finite sets, Colloq. Math. Soc. János Bolyai 10, 1199-1226 (1975; Zbl 0308.05124)]. Subdirect powers of $K_{n}$ or $A_{n}$ are also characterized, and the subdirectly irreducibles of the quasivariety of $n$-colorable graphs for finite $n$ with respect to full and ordinary decompositions are determined. The first type of subdirectly irreducibles are $K_{i} (1\leq i\leq n)$, $A_{n}$ and $B_{n}=K_{n+2}-P_{4}$, where $P_{4}$ is the path having four vertices. The subdirectly irreducibles for full decompositions also include $A_{1},\ldots ,A_{n-1}$ and several weak subgraphs of $B_{n}$, their number growing quadratically with $n$.
Reviewer: I.Tomescu (Bucureşti)