Previous |  Up |  Next


relation; compactness
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ětov 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.
[1] Abramovich Y.A., Arenson E.L., Kitover A.: Banach C(K)-modules and operations preserving disjointness. Berkeley Report no. MSRI 05808-91 (1991). MR 1202880
[2] de Bruijn N.G., Erdös P.: A colour problem for infinite graphs and a problem in the theory of relations. Indagationes Math. 13 (1951), 371-373. MR 0046630
[3] Dreyer P., Malon Ch., Nešetřil J.: Universal H-colorable graphs without a given configuration. KAM-DIMATIA Series 99-428, Discrete Math., to appear. MR 1905979
[4] Frolík Z.: Fixed points of maps of $\beta(\Bbb N)$. Bull. Amer. Math. Soc. 74 (1968), 187-191. MR 0222847
[5] Frolík Z.: Fixed points of maps of extremally disconnected spaces and complete Boolean algebras. Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 16 (1968), 269-275. MR 0233343
[6] Häggkvist R., Hell P.: Universality of $A$-mote graphs. Europ. J. Combinatorics 14 (1993), 21-27. MR 1197472
[7] Hell P., Nešetřil J.: Oriented A-mote graphs. to appear.
[8] Katětov M.: A theorem on mappings. Comment. Math. Univ. Carolinae 8.3 (1967), 431-433. MR 0229228
[9] Krawczyk A., Stepra\`ns J.: Continuous colorings of closed graphs. Topology Appl. 51 (1993), 13-26. MR 1229497
[10] Nešetřil J., Sopena E., Vignal L.: T-preserving homomorphisms of oriented graphs. Comment. Math. Univ. Carolinae 38.1 (1997), 125-136. MR 1455476
[11] Pérennes S.: A proof of Jean de Rumeur's conjecture. Discrete Appl. Math. 74 3 295-299 (1997). MR 1444947 | Zbl 0869.05035
[12] Rumeur J.: Communications dans les réseaux de processeurs. Masson, 1994.
Partner of
EuDML logo