← All problems

Erdős Problem #1175 — Triangle-Free Subgraphs of Prescribed Chromatic Number

1 year old · traced to

For a graph GG, let χ(G)\chi(G) denote its chromatic cardinal: the least cardinality of a set of colors admitting a proper coloring of the vertices of GG. A graph is triangle-free if it has no three distinct vertices joined pairwise by edges. The question is whether, for every uncountable cardinal κ\kappa, there is a cardinal μ\mu such that every graph GG with χ(G)=μ\chi(G)=\mu has a subgraph HH satisfying

χ(H)=κandH is triangle-free.\chi(H)=\kappa \qquad\text{and}\qquad H\text{ is triangle-free}.

Here a subgraph need not be induced. The cardinal μ\mu may depend on κ\kappa; the assertion does not require μ=κ\mu=\kappa. 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)

References

Progress summary

Never refreshed

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.