Abstract
Consistently there exist ℵ2-chromatic graphs with no ℵ1-chromatic subgraphs. The statement that every uncountably chromatic graph of size ℵ1 contains an uncountably chromaticω-connected subgraph is consistent and independent. It is consistent that there is an uncountably chromatic graph of size ℵω 1 in which every subgraph with size less than ℵω 1 is countably chromatic.
Similar content being viewed by others
References
J. E. Baumgartner,Generic graph construction, J. Symb. Logic49 (1984), 234–240.
W. W. Comfort and S. Negrepontis,Chain Conditions in Topology, Cambridge University Press, 1982.
P. Erdös,Problems and results on finite and infinite combinatorial analysis, inInfinite and Finite Sets, Coll. Math. Soc. J. Bolyai, 10 (A. Hajnal, R. Rado and V. T. Sós, eds.), pp. 403–424.
P. Erdös,Problems and results on finite and infinite combinatorial analysis, II, Enseign. Math.27 (1981), 163–176.
P. Erdös,On the combinatorial problems I would most like to see solved, Combinatorica1 (1981), 25–42.
P. Erdös,Problems and results on chromatic numbers in finite and infinite graphs, inGraph Theory with Applications to Algorithms and Computer Science (Y. Alavi, G. Chartrand, L. Lesniak, D. R. Lich and C. E. Wall, eds.), John Wiley and Sons, 1985, pp. 201–213.
P. Erdös and A. Hajnal,On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hung.17 (1966), 61–99.
P. Erdös and A. Hajnal,Chromatic number of finite and infinite graphs and hypergraphs, Discr. Math.53 (1985), 281–285.
M. Foreman,Potent axioms, Trans Am. Math. Soc.294 (1986), 1–28.
M. Foreman and R. Laver,A graph transfer property, to appear.
F. Galvin,Chromatic numbers of subgraphs, Period. Math. Hung.4 (1973), 117–119.
P. Komjáth,Connectivity and chromatic number of infinite graphs, Isr. J. Math.56 (1986), 257–266.
P. Komjáth and S. Shelah,Forcing constructions for uncountable chromatic graphs, J. Symb. Logic, to appear.
S. Shelah,Remarks on cardinal invariants in topology, Gen. Topol. Appl.7 (1977), 251–259.
S. Shelah,A compactness theorem for singular cardinals, free algebras, Whitehead problem, and transversals, Isr. J. Math.21 (1975), 319–349.
S. Shelah,Proper Forcing, Lecture Notes in Math.940, Springer-Verlag, Berlin, 1982.
Author information
Authors and Affiliations
Additional information
Partially supported by Hungarian Science Research Fund Nu. 1805.
Rights and permissions
About this article
Cite this article
Komjáth, P. Consistency results on infinite graphs. Israel J. Math. 61, 285–294 (1988). https://doi.org/10.1007/BF02772573
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02772573