Subdirect decomposition of \(n\)-chromatic graphs (Q1272897): Difference between revisions

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\).