Erdős Problem #922 — Hereditary independence forces bounded chromatic number
Let be a non-negative integer and let be a graph, not necessarily finite. For a finite set , write for the subgraph induced by , and let denote its independence number. Suppose that
for every finite . Must the chromatic number of satisfy ? Erdős Problem #922 Bonamy et al. (2020)
Background
The condition controls how far the independence number of each finite induced subgraph can fall below half its order. At , the requirement that every induced subgraph have independence ratio at least forces to be bipartite: a non-bipartite graph has an induced odd cycle, whose independence number is less than half its order. Erdős and Hajnal raised the question; the problem record notes that they could not prove the case . Erdős Problem #922 Bonamy et al. (2020)
For a finite graph , the potential used in the proof is . The signed deficit is not always a number of vertices that can be deleted. When it is nonnegative, it is exactly the minimum number of vertices whose deletion leaves a half-stable induced subgraph (one with independence ratio at least ); when it is negative, is already half-stable. Thus the potential records this deletion deficit, shifted by two, while remaining defined in both cases. Bonamy et al. (2020)
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.
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.