On 2colored graphs and partitions of boxes
On 2colored graphs and partitions of boxes

Ron Holzman, Technion
Fine Hall 224
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 kclique of each color, then G has at least 4(k1) vertices. This confirms a conjecture of Bucic, Lidicky, Long, and Wagner, and thereby solves the 2dimensional case of their problem about partitions of discrete boxes with the kpiercing property. We also characterize the case of equality in our result.