Colouring arcwise connected sets in the plane. I (Q5935603): Difference between revisions

Let \({\mathcal G}\) be the family of finite collections \({\mathcal S}\) of bounded, arcwise connected sets in the plane such that for any \(S,T\in {\mathcal S}\) with \(S\cap T\neq \emptyset\), \(S\cap T\) is arcwise connected. In this paper the problem of bounding the chromatic number of the intersection graph \(G\) of a collection \({\mathcal S}\in {\mathcal G}\) is investigated. Assume that \(G\) is triangle-free and that there exists a closed Jordan curve \(C\) in the plane such that \(C\) intersects all sets of \({\mathcal S}\), and that for all \(S\in {\mathcal S}\), the following holds: (i) \(S\cap (C\cup \text{int}(C))\) is arcwise connected or \(S\cap \text{int}(C)=\emptyset \); (ii) \(S\cap (C\cup \text{ext}(C))\) is arcwise connected or \(S\cap \text{ext}(C)=\emptyset \) (here \(\text{int}(C)\) and \(\text{ext}(C)\) denote the regions in the interior, resp. exterior, of \(C\)). The main result of the paper asserts that under these conditions \(\chi ({\mathcal S})\) is bounded above by a constant independent of \({\mathcal S}\). This gives an affirmative answer to a problem raised by \textit{A. V. Kostochka} and \textit{J. Nešetřil} [Eur. J. Comb. 19, No. 1, 103-110 (1998; Zbl 0886.05064)].