Distance graphs and \(T\)-coloring (Q1305534)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distance graphs and \(T\)-coloring |
scientific article |
Statements
Distance graphs and \(T\)-coloring (English)
0 references
30 January 2000
0 references
For any set \(D\) of positive integers, the distance graph \(G(Z,D)\) is the graph on all integers with edges connecting them when they are at some numeric distance within \(D\). This paper determines the chromatic and fractional chromatic numbers of \(G(Z,D)\) for any \(D\) of type \(\{1,\ldots,m\}\setminus\{k\}\) as follows. Both equal \(k\) as soon as \(2k>m\); when \(2k\leq m\) and \(r\) \((s)\) is the exponent of 2 in the prime decomposition of \(m+k+1\) \((k)\), then both chromatic numbers equal \(\frac{1}{2}(m+k+1)\) when \(r>s\) and otherwise the chromatic number equals \((m+k+2)\setminus\div 2\). Several cases are identified where the circular chromatic number coincides with the standard one.
0 references
distance graph
0 references
chromatic number
0 references
fractional chromatic number
0 references
circular chromatic number
0 references
\(T\)-coloring ratio
0 references