×

Embedding graphs into colored graphs. (English) Zbl 0659.03029

This paper considers questions of the following types: Given the graph X, what can be said about graphs Y such that whenever the vertices (or the edges) of Y are colored with \(\gamma\) colors, then Y contains a monocolored copy of X (or a monocolored copy of X as an induced subgraph)? Amongst the results are the following. Result 1. If X is a graph on the regular infinite cardinal \(\kappa\), then there is Y on \(2^{\kappa}\) vertices such that every vertex coloring of Y by \(\kappa\) colors has an induced monocolored copy of X; moreover for all ordinals \(\alpha\) such that X does not contain the complete graph \(K_{\alpha}\) on a set of order type \(\alpha\), also Y does not contain \(K_{\alpha}\). Result 2. It is consistent that Result 1 holds for Y on \(\kappa^+\) vertices and \(\kappa^+<2^{\kappa}\). Result 3. It is consistent that there is a graph X on \(\omega_ 1\) vertices for which there is no Y with the property that whenever the edges of Y are colored with two colors, then Y contains an induced monocolored copy of X. (The graph X is actually a bipartite graph on \(\omega\) and \(\omega_ 1\) vertices.) This third result is somewhat unexpected; it was shown by P. Erdős, A. Hajnal and L. Posa [Infinite finite sets, Colloq. Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 585-595 (1975; Zbl 0312.05123)] that such Y does exist whenever \(| X| \leq \omega\).
Reviewer: N.H.Williams

MSC:

03E05 Other combinatorial set theory
03E35 Consistency and independence results
05C15 Coloring of graphs and hypergraphs
05C55 Generalized Ramsey theory

Citations:

Zbl 0312.05123
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Baumgartner and A. Hajnal, A proof (involving Martin’s axiom) of a partition relation, Fund. Math. 78 (1973), no. 3, 193 – 203. · Zbl 0257.02054
[2] James E. Baumgartner, A new class of order types, Ann. Math. Logic 9 (1976), no. 3, 187 – 222. · Zbl 0339.04002
[3] W. Wistar Comfort and Stylianos A. Negrepontis, Chain conditions in topology, Cambridge Tracts in Mathematics, vol. 79, Cambridge University Press, Cambridge-New York, 1982.
[4] Walter Deuber, Partitionstheoreme für Graphen, Comment. Math. Helv. 50 (1975), no. 3, 311 – 320. · Zbl 0313.05120
[5] Keith J. Devlin, Aspects of constructibility, Lecture Notes in Mathematics, Vol. 354, Springer-Verlag, Berlin-New York, 1973. · Zbl 0312.02054
[6] P. Erdős, F. Galvin, and A. Hajnal, On set-systems having large chromatic number and not containing prescribed subsystems, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, North-Holland, Amsterdam, 1975, pp. 425 – 513. Colloq. Math. Soc. János Bolyai, Vol. 10.
[7] P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar 17 (1966), 61 – 99. · Zbl 0151.33701
[8] P. Erdős and A. Hajnal, On decomposition of graphs, Acta Math. Acad. Sci. Hungar. 18 (1967), 359 – 377. · Zbl 0169.26601
[9] P. Erdős and A. Hajnal, On chromatic number of infinite graphs, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 83 – 98.
[10] P. Erdős, A. Hajnal, and L. Pósa, Strong embeddings of graphs into colored graphs, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, North-Holland, Amsterdam, 1975, pp. 585 – 595. Colloq. Math. Soc. János Bolyai, Vol. 10.
[11] P. Erdős, A. Hajnal, and B. Rothchild, ”On chromatic number of graphs and set-systems” (Acta Math. Acad. Sci. Hungar. 17 (1966), 61 – 99) by Erdős and Hajnal, Cambridge Summer School in Mathematical Logic (Cambridge, 1971) Springer, Berlin, 1973, pp. 531 – 538. Lecture Notes in Math., Vol. 337.
[12] Jon Folkman, Graphs with monochromatic complete subgraphs in every edge coloring., SIAM J. Appl. Math. 18 (1970), 19 – 24. · Zbl 0193.53103
[13] Ronald L. Graham, Rudiments of Ramsey theory, CBMS Regional Conference Series in Mathematics, vol. 45, American Mathematical Society, Providence, R.I., 1981. · Zbl 0458.05043
[14] A. Hajnal and J. Pach, Monochromatic paths in infinite coloured graphs, Finite and infinite sets, Vol. I, II (Eger, 1981) Colloq. Math. Soc. János Bolyai, vol. 37, North-Holland, Amsterdam, 1984, pp. 359 – 369. · Zbl 0566.05031
[15] Péter Komjáth, A note on Hajnal-Máté graphs, Studia Sci. Math. Hungar. 15 (1980), no. 1-3, 275 – 276.
[16] Péter Komjáth, The colouring number, Proc. London Math. Soc. (3) 54 (1987), no. 1, 1 – 14. · Zbl 0579.03035
[17] Péter Komjáth and Vojtěch Rödl, Coloring of universal graphs, Graphs Combin. 2 (1986), no. 1, 55 – 60. · Zbl 0589.05053
[18] Kenneth Kunen, Set theory, Studies in Logic and the Foundations of Mathematics, vol. 102, North-Holland Publishing Co., Amsterdam-New York, 1980. An introduction to independence proofs. · Zbl 0443.03021
[19] J. Nešetřil and V. Rödl, A Ramsey graph without triangles exists for any graph without triangles, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. III, North-Holland, Amsterdam, 1975, pp. 1127 – 1132. Colloq. Math. Soc. Janos Bolyai, Vol. 10.
[20] Jaroslav Nešetřil and Vojtěch Rödl, Partitions of vertices, Comment. Math. Univ. Carolinae 17 (1976), no. 1, 85 – 95. · Zbl 0344.05150
[21] Jaroslav Nešetřil and Vojtěch Rödl, On a probabilistic graph-theoretical method, Proc. Amer. Math. Soc. 72 (1978), no. 2, 417 – 421. · Zbl 0399.05007
[22] Saharon Shelah, Colouring without triangles and partition relation, Israel J. Math. 20 (1975), 1 – 12. · Zbl 0311.05112
[23] -, Proper forcing, Lecture Notes in Math., vol. 940, Springer-Verlag, Berlin and New York · Zbl 0495.03035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.