Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs with Distance Sets Missing An Interval

Abstract

Given positive integers \(m, k,\) and \(t\). Let \(D_{m,[k,k+i]} = \{1,2,\ldots,m\} – \{k,k+1,\ldots,k+i\}\). The distance graph \(G(\mathbb{Z}, D_{m,[k,k+i]})\) has vertex set all integers \(\mathbb{Z}\) and edges connecting \(j\) and \(j’\) whenever \(|j-j’| \in D_{m,[k,k+i]}\). The fractional chromatic number, the chromatic number, and the circular chromatic number of \(G(\mathbb{Z}, D_{m,k,i})\) are denoted by \(\chi_f(\mathbb{Z}, D_{m[k,k+i]}), \chi(\mathbb{Z}, D_{m,[k,k+i]}),\) and \(\chi_c(\mathbb{Z}, D_{m,[k,k+i]})\), respectively. For \(i=0\), we simply denote \(D_{m,[k,k+0]}\) by \(D_{m,k}\). \(X(\mathbb{Z}, D_{m,k})\) was studied by Eggleton, Erdős and Skilton [5], Kemnitz and Kolberg [8], and Liu [9], and was completely solved by Chang, Liu and Zhu [1] who also determined \(\chi_c(\mathbb{Z}, D_{m,k})\) for any \(m\) and \(k\). The value of \(\chi_c(\mathbb{Z}, D_{m,k})\) was studied by Chang, Huang and Zhu [2] who finally determined \(\chi_c(\mathbb{Z}, D_{m,k})\) for any \(m\) and \(k\). This paper extends the study of \(G(\mathbb{Z}, D_{m,[k,k+i]})\) to values \(i\) with \(1 \leq i \leq k-1\). We completely determine \(\chi_f(\mathbb{Z}, D_{m,[k,k+i]})\) and \(\chi(\mathbb{Z}, D_{m,k,i})\) for any \(m\) and \(k\) with \(1 \leq i \leq k-1\). However, for \(\chi_c(\mathbb{Z}, D_{m,[k,k+i]})\), only some special cases are determined.