Premium
Integral distance graphs
Author(s) -
Chen JerJeong,
Chang Gerard J.,
Huang KuoChing
Publication year - 1997
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/(sici)1097-0118(199708)25:4<287::aid-jgt6>3.0.co;2-g
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , chromatic scale , discrete mathematics
Suppose D is a subset of all positive integers. The distance graph G ( Z , D ) with distance set D is the graph with vertex set Z , and two vertices x and y are adjacent if and only if | x − y | ≡ D . This paper studies the chromatic number χ( Z , D ) of G ( Z , D ). In particular, we prove that χ( Z , D ) ≤ | D | + 1 when | D | is finite. Exact values of χ( G , D ) are also determined for some D with | D | = 3. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 287–294, 1997