arXiv Analytics

Sign in

arXiv:1810.08920 [math.CO]AbstractReferencesReviewsResources

On 2-colored graphs and partitions of boxes

Ron Holzman

Published 2018-10-21Version 1

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 (arXiv:1805.11278[math.CO]) 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.

Comments: 11 pages, 1 figure
Categories: math.CO, cs.DM
Subjects: 05C15, 05B45
Related articles: Most relevant | Search more
arXiv:2406.00139 [math.CO] (Published 2024-05-31)
Combinatorial proofs of inequalities involving the number of partitions with parts separated by parity
arXiv:2205.04527 [math.CO] (Published 2022-05-09)
Number of partitions of n into parts not divisible by m
arXiv:math/0210195 [math.CO] (Published 2002-10-14)
On a class of algebras defined by partitions

Links

Toolbox