Coloring decompositions of complete geometric graphs (Q2338577)

A geometric graph \(G\) is a drawing in the plane of a simple graph \(G\) such that no three vertices are on a line and edges are straight-line segments. Two geometric graphs have nonempty intersection if they share a vertex or there exists a pair of crossing edges, one from each graph. A decomposition of a geometric graph \(G\) is a pair \([G, P]\) such that \(P\) is a partition of the edges of \(G\). A \(k\)-\(P\)-coloring of a decomposition \([G, P]\) is a mapping from edges of \(G\) to a set of \(k\) colors satisfying the following conditions. (1) All edges of a member in \(P\) are colored the same. (2) If \(H_1, H_2 \in P\) have nonempty intersection, then their edges are colored differently. The chromatic index of \([G, P]\), denoted by \(\chi^\prime([G, P])\), is the smallest positive integer \(k\) for which there is a \(k\)-\(P\)-coloring of \([G, P]\). \par Let \([K_n, P]\) be a decomposition of the complete geometric graph \(K_n\). Then \(\chi^\prime([K_n, P]) \leq \frac{n^2}{6}+O(n^{3/2})\). The upper bound can be strengthened to \(\frac{n^2}{12}+O(n^{3/2})\) if \(P\) does not contain triangles. For every natural number \(n\), there exists some \([K_n, P]\) such that \(\chi^\prime([K_n, P]) \geq \frac{n^2}{24.5}+\Theta (n)\). When the vertices of a complete graph are drawn as the vertices of a regular \(n\)-gon, this complete convex geometric graph is denoted by \(K^c_n\). Then the above lower bound can be raised to \(\chi^\prime([K^c_n, P]) \geq \frac{n^2}{9}-O(n)\). It is also proved that, for every \([K^c_n, P]\) such that all elements in \(P\) are triangles, \(\chi^\prime([K^c_n, P]) \geq \frac{n^2}{119}-O(n)\). Finally, the authors propose the so-called Erdős-Faber-Lovász conjecture for complete geometric graphs as follows. Let \([K_n, P]\) be a decomposition of \(K_n\), then \(\chi^\prime([K_n, P]) \leq \frac{n^2}{9}+\Theta(n)\).