← All problems

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

57 years old · traced to

Let kk be a non-negative integer and let GG be a graph, not necessarily finite. For a finite set U⊆V(G)U\subseteq V(G), write G[U]G[U] for the subgraph induced by UU, and let α(G[U])\alpha(G[U]) denote its independence number. Suppose that

α(G[U])≥∣U∣−k2\alpha(G[U])\geq \frac{|U|-k}{2}

for every finite U⊆V(G)U\subseteq V(G). Must the chromatic number of GG satisfy χ(G)≤k+2\chi(G)\leq k+2? 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 k=0k=0, the requirement that every induced subgraph have independence ratio at least 1/21/2 forces GG 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 k=1k=1. Erdős Problem #922 Bonamy et al. (2020)

For a finite graph HH, the potential used in the proof is ρ(H)=∣V(H)∣−2α(H)+2\rho(H)=|V(H)|-2\alpha(H)+2. The signed deficit ∣V(H)∣−2α(H)|V(H)|-2\alpha(H) 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 1/21/2); when it is negative, HH 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.

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.

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.