Kalai–Meshulam chromatic conjecture on induced cycles

About 6 years old · traced to

Let GG be a graph, and let the chromatic number of GG be its minimum number of colors in a proper vertex coloring. An induced cycle is a cycle whose vertices induce exactly the edges of the cycle.

Kalai–Meshulam chromatic conjecture. A graph with high enough chromatic number has an induced cycle of length divisible by three.

This conjecture was proved by Bonamy, Charbit, and Thomassé, and later generalized by Scott and Seymour.

References

Primary source

Alexander Engstrom, “On the topological Kalai-Meshulam conjecture”, arXiv:2009.11077 (2020).

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.