Erdős Problem #922 — Hereditary independence forces bounded chromatic number

About 57 years old · traced to 1969

Let $k≥0$ . If every finite induced subgraph $H$ of a graph $G$ has an independent set of size at least $(|V(H)|-k)/2$ , must $χ(G)≤k+2$ ?

References

Primary source

P. Erdős, Problems and results in chromatic graph theory, in Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., 1968), Academic Press (1969), 27–35.

Additional references

P. Erdős, Problems and results in chromatic graph theory, in Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., 1968), Academic Press (1969), 27–35.

chromatic-number graph-theory

InErdős Problems

Posted 1 month ago

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.

No solutions have been posted yet.