Coloring relatives of intervals on the plane. I: Chromatic number versus girth (Q1378297): Difference between revisions

The following two types are discussed: For a class \(\mathcal G\) of intersection graphs and for a positive integer \(k\geq 2\) find or bound (1) \(f(\mathcal G,k)\), the maximum chromatic number of a graph in \(\mathcal G\) with a clique number of at most \(k\); and (2) \(g(\mathcal G,k)\), the maximum chromatic number of a graph in \(\mathcal G\) with girth at least \(k\) (here \(k\geq 4\) is assumed). The objects of this paper are the families: \(\mathcal I\)---the intersection graphs of intervals on the plane; \(\mathcal R\)---the intersection graphs of rays on the plane; and \(\mathcal S\)---the intersection graphs of such families of strings (i.e. arcs) on the plane that the intersection of any two strings is a connected subset of the plane. Obviously, \(\mathcal R\subseteq \mathcal I \subseteq \mathcal S\) and thus \(f(\mathcal R,k)\leq f(\mathcal I,k)\leq f(\mathcal S,k)\) and \(g(\mathcal R,k)\leq g(\mathcal I,k)\leq g(\mathcal S,k)\) for every \(k\). Also \(f(\mathcal G,2)= g(\mathcal G,4)\) for every family \(\mathcal G\). The paper brings (among other) the following results: Theorem 1. \[ g(\mathcal S,k)=\begin{cases} 6, \quad k\geq 5;\\ 4, \quad k\geq 6; \\ 3, \quad k\geq 8. \end{cases} \] Theorem 2. For any integer \(k\geq 6\), we have \(g(\mathcal R,k)=3\) and \(g(\mathcal R,5)\leq 4\).