Coloring decompositions of complete geometric graphs
type: Item
instance of: scholarly article
title: Coloring decompositions of complete geometric graphs
zbMATH Open document ID: 1449.05098
author: Clemens Huemer
author: D. Lara
author: Christian Rubio-Montiel
published in: Acta Mathematica Hungarica
publication date: 2019-11-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/1610.01676
review text: 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)\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 7134803
zbMATH Keywords: geometric graph
zbMATH Keywords: coloring
zbMATH Keywords: geometric chromatic index
MaRDI profile type: Publication
OpenAlex ID: W3098231207
arXiv ID: 1610.01676
DOI: 10.1007/S10474-019-00963-0
description: scientific article