Coloring the complements of intersection graphs of geometric figures (Q941403)

The intersection graph \(G\) of a family \(\mathcal{F}\) of sets is the graph with vertex set \(\mathcal{F}\) in which two members of \(\mathcal{F}\) are adjacent if and only if they have nonempty intersection. Let \(\alpha(G)\) and \(\gamma(G)\) denote the size of the maximum independent set and the size of the minimum dominating set of \(G\), respectively. Let \(\chi(G)\) denote the chromatic number of \(G\). Two convex bodies \(K\) and \(D\) in \(\mathbb{R}^n\) are called homothetic if \(K = x + \lambda D\) for a point \(x\) in \(\mathbb{R}^n\) and some positive \(\lambda\). The following results are proved in this paper. {\parindent=7mm \begin{itemize}\item[(i)]Let \(\overline{G}\) be the complement of an intersection graph \(G\) of translations of a fixed compact convex set in the plane. Then \(\chi(\overline{G}) \leq \min\{3\alpha(G)-2, 6\gamma(G)\}\). The bound \(\chi(\overline{G}) \leq 6\gamma(G)\) is sharp. \item[(ii)]Let \(\mathbb{F}\) be a family of translates of a convex body \(M\) in \(\mathbb{R}^n\) for \(n \geq 3\). If \(G\) is the intersection graph of \(\mathbb{F}\), then \(\chi(\overline{G}) \leq \left\lceil 2(n^2-n+1)^{1/2}\right\rceil^{n-1} \left\lceil(n^2-n+1)^{1/2}\right\rceil(\alpha(G)-1)+1\). \item[(iii)]Let \(\mathcal{D}_2\) be a family of homethetic copies of a fixed compact convex set \(D\) in the plane. If \(\overline{G}\) is the complement of the intersection graph \(G\) of \(\mathcal{D}_2\), then \(\chi(\overline{G}) \leq 6\alpha(G)-5.\) \end{itemize}}