Asymptotic clique covering ratios of distance graphs (Q1612760): Difference between revisions

The distance graph \(G(Z,D)\) generated by the set \(D\) of positive integers has integers as vertices and edges \(ij\) with \(|i-j|\in D\). The subgraph of \(G(Z,D)\) induced by \(\{ 0,1,\ldots ,n-1\}\) is denoted by \(G(n,D)\). The paper studies the asymptotic clique covering ratio of \(G(Z,D)\) defined as \(S(D)=\lim\sup_{n\rightarrow\infty}(n/cl(G(n,D))\) where \(cl(G)=\chi (\overline G)\) is the minimum number of cliques in graph \(G\) which cover all its vertices. One of the motivations for the study of \(S(D)\) is to provide lower bounds for the quotient \(sp_T(G)/\chi (G)\), where \(sp_T(G)\) is the minimum span of a \(T\)-coloring of graph \(G\) (a \(T\)-coloring of a graph is a map \(\varphi:V(G)\rightarrow \{0,1,\ldots\}\) with \(|\varphi (x)-\varphi (y)|\not\in T\) for every edge \(xy\) of \(G\), where \(0\in T\) is a set of nonnegative integers). The authors show that, for a finite set \(D\), the value \(S(D)\) can be achieved by a periodic clique covering \(f\) assigning to each integer the clique to which it belongs. Here ``periodic'' means that there is a permutation \(\sigma\) on the image of \(f\) and a positive integer \(p\) such that \(f(x)=\sigma(f(x-p))\) for all \(x\geq p\). As a consequence, the limit in the definition of \(S(D)\) exists and \(S(D)\) is a rational number. The remaining part of the paper is devoted to the study of sets for which \(S(D)=\omega (G(Z,D))\), that is, \(G(Z,D)\) can be partitioned by cliques of maximum size. Some sufficient conditions for this equality to hold in terms of fractional and circular chromatic numbers and regular colorings are given. In connection with \(T\)-colorings, it is shown that, if \(T\) satisfies \(sp_T(G)=sp_T(K_{\chi (G)})\) for each graph \(G\), then \(S(D)=\omega (G(Z,D))\) for \(D=T\setminus \{ 0\}\).