Erdős Problem #1175 — Triangle-Free Subgraphs of Prescribed Chromatic Number
For a graph , let denote its chromatic cardinal: the least cardinality of a set of colors admitting a proper coloring of the vertices of . A graph is triangle-free if it has no three distinct vertices joined pairwise by edges. The question is whether, for every uncountable cardinal , there is a cardinal such that every graph with has a subgraph satisfying
Here a subgraph need not be induced. The cardinal may depend on ; the assertion does not require . Erdős Problems #1175
Background
The question belongs to the study of how much forbidden-subgraph structure can be found inside graphs of large chromatic cardinal. The surrounding classical results give contrasting constraints: Erdős and Hajnal showed that omitting any finite bipartite graph forces a graph to be countably chromatic, while triangle-free graphs of arbitrarily large infinite chromatic cardinal can nevertheless be constructed. The latter existence result does not ensure that such a subgraph occurs inside an arbitrary graph of prescribed chromatic cardinal. Komjáth–Shelah (1988)
For the countable case, the paper reports that Rődl proved every countably chromatic graph contains a countably chromatic triangle-free subgraph. Komjáth and Shelah’s 1988 work addresses the different behavior possible at uncountable chromaticity, constructing models in which an uncountably chromatic graph has no uncountably chromatic triangle-free subgraph. Komjáth–Shelah (1988)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.