2-Distance Colorings of Integer Distance Graphs
2-Distance Colorings of Integer Distance Graphs
复制标题
整数距离图的 2 距离着色
DOI：
10.7151/dmgt.2040
复制
发表时间：
2016
影响因子：
0.7
通讯作者：
Isma Bouchemakh
中科院分区：
文献类型：
--
作者：
Brahim Benmedjdoub;É. Sopena;Isma Bouchemakh
摘要 图 G 的 2 距离 k 着色是从 V (G) 到颜色集 {1,. 。 ., k} 使得距离最多为 2 的每两个顶点接收到不同的颜色。 G 的 2 距离色数 χ2(G) 是 G 允许 2 距离 k 着色的最小 k。对于任何有限正整数集 D = {d1, . 。 ., dℓ}，整数距离图 G = G(D) 是由 V (G) = ℤ 和 uv ∈ E(G) 定义的无限图当且仅当 |v − u| ε D。我们研究几种类型的集合 D 的整数距离图的 2 距离色数。在每种情况下，我们提供该参数的精确值或上限，并用 χ2(G(D)) = Δ(G(D)) + 1 来表征这些图 G(D)。
Abstract A 2-distance k-coloring of a graph G is a mapping from V (G) to the set of colors {1,. . ., k} such that every two vertices at distance at most 2 receive distinct colors. The 2-distance chromatic number χ2(G) of G is then the smallest k for which G admits a 2-distance k-coloring. For any finite set of positive integers D = {d1, . . ., dℓ}, the integer distance graph G = G(D) is the infinite graph defined by V (G) = ℤ and uv ∈ E(G) if and only if |v − u| ∈ D. We study the 2-distance chromatic number of integer distance graphs for several types of sets D. In each case, we provide exact values or upper bounds on this parameter and characterize those graphs G(D) with χ2(G(D)) = ∆(G(D)) + 1.