Premium
Circular chromatic number of distance graphs with distance sets of cardinality 3
Author(s) -
Zhu Xuding
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10062
Subject(s) - mathematics , combinatorics , vertex (graph theory) , conjecture , chromatic scale , discrete mathematics , critical graph , graph , graph power , line graph
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 graphs G ( R , D ) with | D | = 3. As a consequence, we determine the chromatic numbers of all such distance graphs. This settles a conjecture proposed independently by Chen et al. [J. Chen, G. Chang, and K. Huang, J Graph Theory 25 (1997) 281–287 and Voigt [M. Voigt Ars Combinatoria, 52 (1999) 3–12] in the affirmative. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 195–207, 2002