Three-and-more set theorems
Hell, Pavol ; Nešetřil, Jaroslav ; Raspaud, André ; Sopena, Eric
Commentationes Mathematicae Universitatis Carolinae, Tome 41 (2000), p. 793-801 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2000-01-01
Classification:  05C05,  05C15,  05C99,  05D05 
@article{119210,
     author = {Pavol Hell and Jaroslav Ne\v set\v ril and Andr\'e Raspaud and Eric Sopena},
     title = {Three-and-more set theorems},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {41},
     year = {2000},
     pages = {793-801},
     zbl = {1045.05086},
     mrnumber = {1800165},
     language = {en},
     url = {http://dml.mathdoc.fr/item/119210}
}

Hell, Pavol; Nešetřil, Jaroslav; Raspaud, André; Sopena, Eric. Three-and-more set theorems. Commentationes Mathematicae Universitatis Carolinae, Tome 41 (2000) pp. 793-801. http://gdmltest.u-ga.fr/item/119210/

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

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. (1951) | MR 0046630

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

Frolík Z. Fixed points of maps of $\beta(\Bbb N)$, Bull. Amer. Math. Soc. 74 (1968), 187-191. (1968) | MR 0222847

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. (1968) | MR 0233343

Häggkvist R.; Hell P. Universality of $A$-mote graphs, Europ. J. Combinatorics 14 (1993), 21-27. (1993) | MR 1197472

Hell P.; Nešetřil J. Oriented A-mote graphs, to appear.

Katětov M. A theorem on mappings, Comment. Math. Univ. Carolinae 8.3 (1967), 431-433. (1967) | MR 0229228

Krawczyk A.; Stepra\`Ns J. Continuous colorings of closed graphs, Topology Appl. 51 (1993), 13-26. (1993) | MR 1229497

Nešetřil J.; Sopena E.; Vignal L. T-preserving homomorphisms of oriented graphs, Comment. Math. Univ. Carolinae 38.1 (1997), 125-136. (1997) | MR 1455476

Pérennes S. A proof of Jean de Rumeur's conjecture, Discrete Appl. Math. 74 3 295-299 (1997). (1997) | MR 1444947 | Zbl 0869.05035

Rumeur J. Communications dans les réseaux de processeurs, Masson, 1994.