The ACO Seminar (2019–2020)

We prove that if the edges of a graph $G$ can be colored blue or red in such a way that every vertex belongs to a monochromatic $k$-clique of each color, then $G$ has at least $4(k-1)$ vertices. This confirms a conjecture of Bucic, Lidicky, Long, and Wagner, and thereby solves the 2-dimensional case of their problem about partitions of discrete boxes with the $k$-piercing property. We also characterize the case of equality in our result.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.