{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T19:27:17Z","timestamp":1757705237941},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":9323,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1988,9]]},"abstract":"<jats:p>In this paper we solve some of P\u00e1l Erd\u0151s's favorite problems on uncountably chromatic graphs. Generalizing a finite graph theory result of Tutte, Erd\u0151s and R. Rado showed that for every infinite cardinal \u03ba there exists a triangle-free, <jats:italic>\u03ba<\/jats:italic>-chromatic graph of size <jats:italic>\u03ba<\/jats:italic>. For <jats:italic>\u03ba<\/jats:italic> = \u2135<jats:sub>0<\/jats:sub>, Erd\u0151s established the existence of \u2135<jats:sub>0<\/jats:sub>-chromatic graphs excluding even <jats:italic>C<\/jats:italic><jats:sub>4<\/jats:sub>, <jats:italic>C<\/jats:italic><jats:sub>5<\/jats:sub>,\u2026, <jats:italic>C<jats:sub>n<\/jats:sub><\/jats:italic>, i.e. circuits up to a given length. For <jats:italic>\u03ba<\/jats:italic> &lt; \u2135<jats:sub>0<\/jats:sub> the situation is different. As shown by Erd\u0151s and A. Hajnal, a graph is necessarily countably chromatic if it omits any finite bipartite graph. We can, however, exclude any finite list of nonbipartite graphs (this obviously reduces to excluding finitely many odd circuits). They posed an even stronger conjecture, namely, that similar examples must occur in every uncountably chromatic graph. To be specific, they conjectured that for every infinite <jats:italic>\u03ba<\/jats:italic>, every <jats:italic>\u03ba<\/jats:italic>-chromatic graph contains a <jats:italic>\u03ba<\/jats:italic>-chromatic triangle-free subgraph. Here we show that this may not be true for <jats:italic>\u03ba<\/jats:italic> = \u2135<jats:sub>1<\/jats:sub> i.e. we exhibit a model where it is false. We must emphasize that the conjecture is probably false already in ZFC, but we have been unable to show this.<\/jats:p>","DOI":"10.2307\/2274566","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:27:13Z","timestamp":1146940033000},"page":"696-707","source":"Crossref","is-referenced-by-count":7,"title":["Forcing constructions for uncountably chromatic graphs"],"prefix":"10.1017","volume":"53","author":[{"given":"P\u00e9ter","family":"Komj\u00e1th","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saharon","family":"Shelah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200041980_ref004","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/013.1\/0280381"},{"key":"S0022481200041980_ref014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21543-2"},{"key":"S0022481200041980_ref013","doi-asserted-by":"publisher","DOI":"10.2307\/2041460"},{"key":"S0022481200041980_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90015-0"},{"key":"S0022481200041980_ref001","first-page":"403","volume-title":"Infinite and finite sets","volume":"10","author":"Erd\u0151s","year":"1975"},{"key":"S0022481200041980_ref011","unstructured":"Komj\u00e1th P. , Mekler A. , and Pach J. , Universal graphs (to appear)."},{"key":"S0022481200041980_ref010","first-page":"275","article-title":"A note on the Hajnal-M\u00e1t\u00e9 graphs","volume":"15","author":"Komj\u00e1th","year":"1980","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"key":"S0022481200041980_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760522"},{"key":"S0022481200041980_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579156"},{"key":"S0022481200041980_ref007","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.68.1.142"},{"key":"S0022481200041980_ref006","doi-asserted-by":"publisher","DOI":"10.1137\/0118004"},{"key":"S0022481200041980_ref002","first-page":"163","article-title":"Problems and results on finite and infinite combinatorial analysis. II","volume":"27","author":"Erd\u0151s","year":"1981","journal-title":"L'Enseignement Math\u00e9matique"},{"key":"S0022481200041980_ref009","first-page":"347","volume-title":"Logic Colloquium '73","author":"Hajnal","year":"1975"},{"key":"S0022481200041980_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90148-7"},{"key":"S0022481200041980_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579174"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200041980","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T15:16:43Z","timestamp":1558365403000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200041980\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,9]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1988,9]]}},"alternative-id":["S0022481200041980"],"URL":"https:\/\/doi.org\/10.2307\/2274566","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,9]]}}}