Subdirect Decomposition of n-Chromatic Graphs
Xavier Caicedo
DOI: 10.1023/A:1008637811027
Abstract
It is shown that any n-chromatic graph is a full subdirect product of copies of the complete graphs K n and K n+1, except for some easily described graphs which are full subdirect products of copies of K n+1 - {^\circ -^\circ } and K n+2 - {^\circ -^\circ }; full means here that the projections of the decomposition are epimorphic in edges. This improves some results of Sabidussi. Subdirect powers of K n or K n+1 - {^\circ -^\circ } are also characterized, and the subdirectly irreducibles of the quasivariety of n -colorable graphs with respect to full and ordinary decompositions are determined.
Pages: 157–168
Keywords: graphs; $n$-colorable graph; subdirectly irreducible; subdirect product; quasivariety
Full Text: PDF
References
1. G. Birkhoff, “Subdirect unions in universal algebra,” Bulletin of the A.M.S. 50 (1944), 764-768.
2. J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, American Elsevier, 1977.
3. S. Burris, “Subdirect representation in axiomatic classes,” Colloquium Mathematicum XXXIV(2) (1976), 191-197.
4. S. Burris, “Model companions for finitely generated universal Horn classes,” Journal of Symbolic Logic 49 (1984), 68-74.
5. S. Burris and H. Werner, “Sheaf constructions and their elementary properties,” Transactions of the A.M.S. 248 (1979), 269-309.
6. X. Caicedo, “The subdirect decomposition theorem for classes of structures closed under direct limits,” Journal of the Australian Math. Soc. (Series A) 30 (1980), 171-179.
7. X. Caicedo, “Finitely axiomatizable quasivarieties of graphs,” Algebra Universalis 34 (1995), 314-321.
8. I. Fleischer, “Subdirect decomposability into irreducibles,” Algebra Universalis 16 (1983), 261-263.
9. G. Gratzer, Universal Algebra, 2nd edition, Springer-Verlag, New York, 1979.
10. A.I. Malcev, The Metamathematics of Algebraic Systems, Chap. 5, North Holland, 1971.
11. E. McAllister, “Grafos n-colorables subdirectamente irreducibles,” Master's dissertation, Universidad de Los Andes, Bogotá, 1989.
12. J. Ne\?set\?ril and A. Pultr, “On classes of relations and graphs determined by subobjects and factorobjects,” Discrete Mathematics 22 (1978), 287-300.
13. H.E. Pickett, “Subdirect representation of relational systems,” Fundamenta Mathematicae 56 (1964), 223- 240.
14. A. Pultr and J. Vinarek, “Productive classes and subdirect irreducibility, in particular for graphs,” Discrete Mathematics 20 (1977), 159-167.
15. G. Sabidussi, “Subdirect representation of graphs,” in Infinite and Finite Sets, Hajnal, Radó, and Los (Eds.), Vol. 3, pp. 1199-1226. Colloq. Math. Janos Bolyai, Vol. 10, North Holland, Amsterdam, 1975.
16. W. Taylor, “Atomic compactness and graph theory,” Fundamenta Mathematicae LXV (1969), 139-145.
17. W.H. Wheeler, “The first order theory of n-colorable graphs,” Transactions of the A.M.S. 258 (1979), 289-310.
2. J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, American Elsevier, 1977.
3. S. Burris, “Subdirect representation in axiomatic classes,” Colloquium Mathematicum XXXIV(2) (1976), 191-197.
4. S. Burris, “Model companions for finitely generated universal Horn classes,” Journal of Symbolic Logic 49 (1984), 68-74.
5. S. Burris and H. Werner, “Sheaf constructions and their elementary properties,” Transactions of the A.M.S. 248 (1979), 269-309.
6. X. Caicedo, “The subdirect decomposition theorem for classes of structures closed under direct limits,” Journal of the Australian Math. Soc. (Series A) 30 (1980), 171-179.
7. X. Caicedo, “Finitely axiomatizable quasivarieties of graphs,” Algebra Universalis 34 (1995), 314-321.
8. I. Fleischer, “Subdirect decomposability into irreducibles,” Algebra Universalis 16 (1983), 261-263.
9. G. Gratzer, Universal Algebra, 2nd edition, Springer-Verlag, New York, 1979.
10. A.I. Malcev, The Metamathematics of Algebraic Systems, Chap. 5, North Holland, 1971.
11. E. McAllister, “Grafos n-colorables subdirectamente irreducibles,” Master's dissertation, Universidad de Los Andes, Bogotá, 1989.
12. J. Ne\?set\?ril and A. Pultr, “On classes of relations and graphs determined by subobjects and factorobjects,” Discrete Mathematics 22 (1978), 287-300.
13. H.E. Pickett, “Subdirect representation of relational systems,” Fundamenta Mathematicae 56 (1964), 223- 240.
14. A. Pultr and J. Vinarek, “Productive classes and subdirect irreducibility, in particular for graphs,” Discrete Mathematics 20 (1977), 159-167.
15. G. Sabidussi, “Subdirect representation of graphs,” in Infinite and Finite Sets, Hajnal, Radó, and Los (Eds.), Vol. 3, pp. 1199-1226. Colloq. Math. Janos Bolyai, Vol. 10, North Holland, Amsterdam, 1975.
16. W. Taylor, “Atomic compactness and graph theory,” Fundamenta Mathematicae LXV (1969), 139-145.
17. W.H. Wheeler, “The first order theory of n-colorable graphs,” Transactions of the A.M.S. 258 (1979), 289-310.