Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Embedding graphs into colored graphs


Authors: A. Hajnal and P. Komjáth
Journal: Trans. Amer. Math. Soc. 307 (1988), 395-409
MSC: Primary 05C55; Secondary 03E35, 04A20, 05A17
DOI: https://doi.org/10.1090/S0002-9947-1988-0936824-0
Corrigendum: Trans. Amer. Math. Soc. 332 (1992), null.
MathSciNet review: 936824
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: If $ X$ is a graph, $ \kappa $ a cardinal, then there is a graph $ Y$ such that if the vertex set of $ Y$ is $ \kappa $-colored, then there exists a monocolored induced copy of $ X$; moreover, if $ X$ does not contain a complete graph on $ \alpha $ vertices, neither does $ Y$. This may not be true, if we exclude noncomplete graphs as subgraphs.

It is consistent that there exists a graph $ X$ such that for every graph $ Y$ there is a two-coloring of the edges of $ Y$ such that there is no monocolored induced copy of $ X$. Similarly, a triangle-free $ X$ may exist such that every $ Y$ must contain an infinite complete graph, assuming that coloring $ Y$'s edges with countably many colors a monocolored copy of $ X$ always exists.


References [Enhancements On Off] (What's this?)

  • [1] J. E. Baumgartner and A. Hajnal, A proof (involving Martin's axiom) of a partition relation, Fund. Math. 78 (1973), 193-203. MR 0319768 (47:8310)
  • [2] J. E. Baumgartner, A new class of order types, Ann. Math. Logic 9 (1976), 187-222. MR 0416925 (54:4988)
  • [3] W. W. Comfort and S. Negrepontis, Chain conditions in topology, Cambridge Tracts in Math., no. 79, Cambridge Univ. Press, 1982. MR 665100 (84k:04002)
  • [4] W. Deuber, Partitionstheoreme für Graphen, Math. Helv. 50 (1975), 311-320. MR 0401546 (53:5373)
  • [5] K. J. Devlin, Aspects of constructibility, Lecture Notes in Math., vol. 354, Springer-Verlag, Berlin and New York, 1973. MR 0376351 (51:12527)
  • [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. Math. Soc. János. Bolyai, no. 19 (Keszthely, Hungary), 1973, pp. 425-513. MR 0398876 (53:2727)
  • [7] P. Erdös and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61-99. MR 0193025 (33:1247)
  • [8] -, On decompositions of graphs, Acta Math. Acad. Sci. Hungar. 18 (1967), 359-377. MR 0223261 (36:6309)
  • [9] -, On chromatic number of infinite graphs, Theory of Graphs (Proc. Colloq., Tihany, 1966) P. Erdös and G. Katona, eds.), Academic Press, New York, 1968, pp. 83-89. MR 0263693 (41:8294)
  • [10] P. Erdös, A. Hajnal and L. Pósa, Strong embedding of graphs into colored graphs, Infinite and Finite Sets (Keszthely, 1973), Colloq. Math. Soc. János Bolyai, no. 10, pp. 585-595. MR 0382049 (52:2937)
  • [11] P. Erdös, A. Hajnal and B. Rothschild, On chromatic number of graphs and set systems, Cambridge Summer School in Mathematical Logic (Cambridge, England, 1971), Lecture Notes in Math., vol. 337, Springer-Verlag and New York, 1973, pp. 531-538. MR 0387103 (52:7949)
  • [12] J. Folkman, Graphs with monochromatic complete subgraphs in every edge coloring, SIAM Appl. Math. 18 (1970), 19-24. MR 0268080 (42:2979)
  • [13] R. L. Graham, Rudiments of Ramsey theory, C.B.M.S. Regional Conf. Ser. Math, no. 45, Amer. Math. Soc., Providence, R. I., 1981. MR 608630 (82j:05018)
  • [14] A. Hajnal and J. Pach, Monochromatic paths in infinite coloured graphs, Finite and Infinite Sets, Colloq. Math. Soc. János Bolyai, no. 37, (Eger, Hungary, 1981), 1984, pp. 359-369. MR 818247 (87d:05076)
  • [15] P. Komjáth, A note on Hajnal-Máté graphs, Studia Sci. Math. Hungar. 15 (1980), 275-276. MR 681447 (84e:03057)
  • [16] -, The colouring number, Proc. London Math. Soc. 54 (1987), 1-14. MR 872247 (88d:05063)
  • [17] P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs and Combinatorics 2 (1986), 55-61. MR 1117132 (92e:05078)
  • [18] K. Kunen, Set theory, An introduction to independence proofs, North-Holland, 1980. MR 597342 (82f:03001)
  • [19] J. Nesetril and V. Rödl, A Ramsey graph without triangles exists for any graph without triangles, Infinite and Finite Sets, Colloq. Math. Soc. János Bolyai, no. 10 (Keszthely, Hungary), 1973, pp. 1127-1132. MR 0392695 (52:13512)
  • [20] -, Partitions of vertices, Comment. Math. Univ. Carolin. 17 (1976), 85-95. MR 0412044 (54:173)
  • [21] -, On a probabilistic graph-theoretical method, Proc. Amer. Math. Soc. 72 (1978), 417-421. MR 507350 (80a:05158)
  • [22] S. Shelah, Colouring without triangles and partition relations, Israel J. Math. 20 (1975), 1-12. MR 0427073 (55:109)
  • [23] -, Proper forcing, Lecture Notes in Math., vol. 940, Springer-Verlag, Berlin and New York,

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C55, 03E35, 04A20, 05A17

Retrieve articles in all journals with MSC: 05C55, 03E35, 04A20, 05A17


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1988-0936824-0
Keywords: Infinite graphs, Ramsey theory, independence, forcing, hypergraphs, chromatic number
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society