Degree-doubling graph families (Q2870523)

For a hypergraph \(H\), a rainbow coloring is a coloring of the vertices of \(H\) such that no hyperedge of \(H\) contains two vertices of the same color. Let \(\chi_r(H)\) be the rainbow chromatic number of \(H\), that is, the smallest cardinal number of colors in a rainbow coloring of \(H\).NEWLINENEWLINEFor a non-empty finite set \(F\) of points of the plane, let \((\mathbb{R}^2,E(F))\) be the \(|F|\)-uniform hypergraph with the vertex set \(\mathbb{R}^2\) and with hyperedges corresponding to congruent copies of \(F\) in \(\mathbb{R}^2\). The maximum Euclidean distance between two points of \(F\) is denoted by \(M(F)\) and the minimum Euclidean distance between two distinct points of \(F\) by \(m(F)\).NEWLINENEWLINEThe author provides some estimates on \(\chi_r(\mathbb{R}^2,E(F))\) for point sets \(F\) with bounded \(M(F)/m(F)\). For example, \(\chi_r(\mathbb{R}^2,E(F)) \leq 7\) is shown for every finite point set \(F\) of size at least 3 satisfying \(M(F)/m(F) \leq \sqrt{7}/2\). Using a different coloring of the plane, the author shows the bound \(\chi_r(\mathbb{R}^2,E(F)) \leq n^2\) provided \(F\) is a finite set of points of size at least 3 satisfying \(M(F)/m(F) \leq (n-1)\frac{\sqrt{3}}{2}\) for some integer \(n\geq 2\). Various other bounds for \(\chi_r(\mathbb{R}^2,E(F))\) are also considered in the paper.