For positive integers w and k, two vectors A and B from Z(w) are called k-crossing if there are two coordinates i and j such that A[i] - B[i] >= k and B[j] - A[j] >= k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k-crossing ...
Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the ...
We answer several questions posed by Beck, Cox, Delgado, Gubeladze, Haase, Hibi, Higashitani, and Maclagan in [Cox et al. 14, Question 3.5 (1),(2), Question 3.6], [Beck et al. 15, Conjecture 3.5(a),(b)], and [Hasse et al. 07, Open question 3 (a),(b) p. 231 ...
The well-known "necklace splitting theorem" of Alon (1987) asserts that every k-colored necklace can be fairly split into q parts using at most t cuts, provided k(q - 1)
In the 1970s Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer k we construct a triangle-free fam ...
A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line L if the intersection of any member with L is a nonempty segment. It is proved that the intersection graphs of simple families of com ...
