Coloring decompositions of complete geometric graphs

DOI10.1007/S10474-019-00963-0MaRDI QIDQ2338577zbMATH OpenOpenAlexFDO

Authors Clemens Huemer, D. Lara, Christian Rubio-Montiel

Publication date 21 November 2019

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.01676

zbMATH Keywords

coloringgeometric chromatic indexgeometric graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A decomposition of a non-empty simple graph $G$ is a pair $[G,P]$, such that $P$ is a set of non-empty induced subgraphs of $G$, and every edge of $G$ belongs to exactly one subgraph in $P$. The chromatic index $ch{i}^{\prime }([G,P])$ of a decomposition $[G,P]$ is the smallest number $k$ for which there exists a $k$-coloring of the elements of $P$ in such a way that: for every element of $P$ all of its edges have the same color, and if two members of $P$ share at least one vertex, then they have different colors. A long standing conjecture of ErdH{o}s-Faber-Lov'asz states that every decomposition $[K_n,P]$ of the complete graph $K_n$ satisfies $ch{i}^{\prime }([K_n,P])leqn$. In this paper we work with geometric graphs, and inspired by this formulation of the conjecture, we introduce the concept of chromatic index of a decomposition of the complete geometric graph. We present bounds for the chromatic index of several types of decompositions when the vertices of the graph are in general position. We also consider the particular case in which the vertices are in convex position and present bounds for the chromatic index of a few types of decompositions.

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)\).

Recommendations

• On the chromatic index of path decompositions
• Geometric achromatic and pseudoachromatic indices
• Chromatically supremal decompositions of graphs
• A note on the Erdős-Faber-Lovász conjecture: quasigroups and complete digraphs.
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane

Cited in

(7)

• Coloring planar perfect graphs by decomposition
• Chromatically supremal decompositions of graphs
• A note on the Erdős-Faber-Lovász conjecture: quasigroups and complete digraphs.
• scientific article; zbMATH DE number 973934 (Why is no real title available?)
• A note on the k-colored crossing ratio of dense geometric graphs
• Partial coloring, vertex decomposability and sequentially Cohen-Macaulay simplicial complexes
• Coloring the complements of intersection graphs of geometric figures

This page was built for publication: Coloring decompositions of complete geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2338577)