P. Hell, J. Ne\v set\v ril, A. Raspaud, E. Sopena
Three-and-more set theorems

Comment.Math.Univ.Carolinae 41,4 (2000) 793-801.

Abstract:In this paper we generalize classical 3-set theorem related to stable partitions of arbitrary mappings due to Erd\H {o}s-de Bruijn, Kat\v etov and Kasteleyn. We consider a structural generalization of this result to partitions preserving sets of inequalities and characterize all finite sets of such inequalities which can be preserved by a ``small'' coloring. These results are also related to graph homomorphisms and (oriented) colorings.

Keywords: relation, compactness
AMS Subject Classification: 05C05, 05C99

PDF