{
  "id": "1810.08920",
  "version": "v1",
  "published": "2018-10-21T09:45:38.000Z",
  "updated": "2018-10-21T09:45:38.000Z",
  "title": "On 2-colored graphs and partitions of boxes",
  "authors": [
    "Ron Holzman"
  ],
  "comment": "11 pages, 1 figure",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-10-21T09:45:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05B45"
    ],
    "keywords": [
      "partitions",
      "vertex belongs",
      "monochromatic k-clique",
      "discrete boxes",
      "colored blue"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}