Coloring of integer distance graphs

被引：36

作者：

Kemnitz, A ^{[1
]}

Kolberg, H ^{[1
]}

机构：

[1] Tech Univ Braunschweig, D-38106 Braunschweig, Germany

来源：

DISCRETE MATHEMATICS | 1998年 / 191卷 / 1-3期

关键词：

distance graphs; chromatic number;

D O I：

10.1016/S0012-365X(98)00099-5

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An integer distance graph is a graph G(D) with the set of integers as vertex set and with an edge joining two vertices u and u if and only if \u - v\ is an element of D where D is a subset of the positive integers. We determine the chromatic number chi(D) of G(D) for some finite distance sets D such as sets of consecutive integers and special sets of cardinality 4. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：113 / 123

页数：11

共 16 条

[1]

DEUBER WA, 1995, CHROMATIC NUMBER DIS

[2]

Eggleton R.B., 1988, DISCRETE MATH, V69, P105

[3] COLORING THE REAL LINE [J].

EGGLETON, RB ;

ERDOS, P ;

SKILTON, DK .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 39 (01) :86-100

[4] COLORING PRIME DISTANCE GRAPHS [J].

EGGLETON, RB ;

ERDOS, P ;

SKILTON, DK .

GRAPHS AND COMBINATORICS, 1990, 6 (01) :17-32

[5]

Frobenius G, 1912, SITZBER K PREUSS AKA, P456

[6]

Hadwiger H., 1961, ELEM MATH, V16, P103

[7]

Jensen T. R., 1995, Graph Coloring Problems

[8]

KOLBERG H, 1996, THESIS TU BRAUNSCHWE

[9]

MENDELSOHN NS, 1970, ANN NY ACAD SCI, V175, P287, DOI 10.1111/j.1749-6632.1970.tb45144.x

[10]

Moser L., 1961, CANAD MATH B, V4, P187

← 1 2 →