𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Circular Chromatic Numbers of Distance Graphs with Distance Sets Missing Multiples

✍ Scribed by Lingling Huang; Gerard J Chang

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
114 KB
Volume
21
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

Given positive integers m, k, s with m > sk, let D m,k,s represent the set {1, 2, . . . , m}{k, 2k, . . . , sk}. The distance graph G(Z , D m,k,s ) has as vertex set all integers Z and edges connecting i and j whenever |i -j| ∈ D m,k,s . This paper investigates chromatic numbers and circular chromatic numbers of the distance graphs G(Z , D m,k,s ). Deuber and Zhu [8] and Liu [13] have shown that m+sk+1 s+1 ≀ Ο‡(G(Z , D m,k,s )) ≀ m+sk+1 s+1 + 1 when m β‰₯ (s + 1)k. In this paper, by establishing bounds for the circular chromatic number Ο‡ c (G(Z , D m,k,s )) of G(Z , D m,k,s ), we determine the values of Ο‡(G(Z , D m,k,s )) for all positive integers m, k, s and Ο‡ c (G(Z , D m,k,s )) for some positive integers m, k, s.

πŸ“œ SIMILAR VOLUMES

Distance graphs with missing multiples i
Distance graphs with missing multiples in the distance sets
✍ Liu, Daphne D.-F.; Zhu, Xuding πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 141 KB πŸ‘ 3 views

Given positive integers m, k, and s with m > ks, let D m,k,s represent the set {1, 2, . . . , m} -{k, 2k, . . . , sk}. The distance graph G(Z, D m,k,s ) has as vertex set all integers Z and edges connecting i and j whenever |i -j| ∈ D m,k,s . The chromatic number and the fractional chromatic number

Circular chromatic number of distance gr
Circular chromatic number of distance graphs with distance sets of cardinality 3
✍ Xuding Zhu πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 104 KB

## Abstract Suppose __D__ is a subset of __R__^+^. The distance graph __G__(__R, D__) is the graph with vertex set __R__ in which two vertices __x__,__y__ are adjacent if |__x__βˆ’__y__| ∈ __D__. This study investigates the circular chromatic number and the fractional chromatic number of distance gra

Circular Chromatic Numbers and Fractiona
Circular Chromatic Numbers and Fractional Chromatic Numbers of Distance Graphs
✍ G.J. Chang; L. Huang; X. Zhu πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 171 KB

This paper studies circular chromatic numbers and fractional chromatic numbers of distance graphs G(Z , D) for various distance sets D. In particular, we determine these numbers for those D sets of size two, for some special D sets of size three, for

Distance Graphs with Finite Chromatic Nu
Distance Graphs with Finite Chromatic Number
✍ I.Z. Ruzsa; Zs. Tuza; M. Voigt πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 96 KB

The distance graph G(D) with distance set D={d 1 , d 2 , ...} has the set Z of integers as vertex set, with two vertices i, j Β₯ Z adjacent if and only if |i -j| Β₯ D. We prove that the chromatic number of G(D) is finite whenever inf{d i+1 /d i } > 1 and that every growth speed smaller than this admit

Fractional chromatic number and circular
Fractional chromatic number and circular chromatic number for distance graphs with large clique size
✍ Daphne Der-Fen Liu; Xuding Zhu πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 136 KB

## Abstract An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005. Let __M__ be a set of positive integers. The distance graph generated by __M__, denoted by __G__(__Z, M__), has the set __Z__ of all integers as the vertex set, and edges __ij__ whenever |__i__