Subdirect Decomposition of n-Chromatic Graphs |
| |
| Authors: | Xavier Caicedo |
| |
| Affiliation: | (1) Departamento de Matemáticas, Universidad de los Andes, Apartado Aéreo 4976, Bogotá, Colombia;(2) Departamento de Matemáticas y Estadística, Universidad Nacional de Colombia, Columbia |
| |
| Abstract: | It is shown that any n-chromatic graph is a full subdirect product of copies of the complete graphs Kn and Kn+1, except for some easily described graphs which are full subdirect products of copies of Kn+1 - {°-°} and Kn+2 - {°-°}; full means here that the projections of the decomposition are epimorphic in edges. This improves some results of Sabidussi. Subdirect powers of Kn or Kn+1 - {°-°} are also characterized, and the subdirectly irreducibles of the quasivariety of n -colorable graphs with respect to full and ordinary decompositions are determined. |
| |
| Keywords: | graphs n-colorable graph subdirectly irreducible subdirect product quasivariety |
| 本文献已被 SpringerLink 等数据库收录！ |
|
