
From the article: We consider graphs \({\mathcal G}=(X,R)\) where the vertex set \(X\) is a standard Borel space (i.e., a complete separable metrizable space equipped with its \(\sigma\)-algebra of Borel sets), and the edge relation \(R\subseteq X^2\) is ``definable,'' i.e., Borel, analytic, coanalytic, etc. A Borel \(n\)-coloring of such a graph, where \(1\leq n\leq\aleph_0\), is a Borel map \(c:X\to Y\) with \(\text{card}(Y)=n\), such that \(xRy\Rightarrow c(x)\neq c(y)\). If such a Borel coloring exists we define the Borel chromatic number of \({\mathcal G}\), in symbols \(\chi_B({\mathcal G})\), to be the smallest such \(n\). Otherwise we say that \({\mathcal G}\) has uncountable Borel number, in symbols \(\chi_B({\mathcal G})>\aleph_0\). The many areas investigated include: examples of Borel graphs \({\mathcal G}\) for which the usual chromatic number \(\chi({\mathcal G})\) is small while its Borel chromatic number \(\chi_B({\mathcal G})\) is large; a complete analysis of the situation in which \(\chi_B({\mathcal G})>\aleph_0\); showing that in the case of the graph \({\mathcal G}_F\) generated by a single Borel function \(F\), \(\chi_B({\mathcal G})\) takes on the values and only the values 1, 2, 3, and \(\aleph_0\). Some open problems are posed, e.g., the authors ask for examples, if any, of acyclic Borel graphs \({\mathcal G}\) satisfying \(3<\chi_B({\mathcal G})<\aleph_0\).
Mathematics(all), Borel chromatic number, Borel coloring, Borel function, 004, Borel space, Coloring of graphs and hypergraphs, Borel sets, Borel graphs, Descriptive set theory, uncountable Borel number
Mathematics(all), Borel chromatic number, Borel coloring, Borel function, 004, Borel space, Coloring of graphs and hypergraphs, Borel sets, Borel graphs, Descriptive set theory, uncountable Borel number
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 105 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 1% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
