Colouring Arcwise Connected Sets in the Plane I

Let ? be the family of finite collections ? where ? is a collection of bounded, arcwise connected sets in ℝ² which for any S, T∈? where S∩T≠∅, it holds that S∩T is arcwise connected. We investigate the problem of bounding the chromatic number of the intersection graph G of a collection ?∈?.

 Assuming G is triangle-free, suppose there exists a closed Jordan curve C⊂ℝ² such that C intersects all sets of ? and for all S∈?, the following holds:

(i) S∩(C∪int (C)) is arcwise connected or S∩int (C)=∅.

(ii) S∩(C∪ext (C)) is arcwise connected or S∩ext (C)=∅.

 Here int(C) and ext (C) denote the regions in the interior, resp. exterior, of C. Such being the case, we shall show that χ(?) is bounded by a constant independent of ?.

Authors and Affiliations

1. Department of Mathematics, University of Umeå, S-90187 Umeå, Sweden e-mail: sean@abel.math.umu.se, , , , , , SE

   Sean McGuinness

Revised: December 3, 1998

Reprints and permissions