|Table of Contents|

[1] Xu Kexiang, Song Zengmin,. Coloring of some integer distance graphs [J]. Journal of Southeast University (English Edition), 2003, 19 (4): 418-422. [doi:10.3969/j.issn.1003-7985.2003.04.024]
Copy

Coloring of some integer distance graphs()
某些整数距离图的染色
Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
19
Issue:
2003 4
Page:
418-422
Research Field:
Mathematics, Physics, Mechanics
Publishing date:
2003-12-30

Info

Title:
Coloring of some integer distance graphs
某些整数距离图的染色
Author(s):
Xu Kexiang1;  Song Zengmin2
1College of Sciences, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
2Department of Mathematics, Southeast University, Nanjing 210096, China
许克祥;  宋增民
南京航空航天大学理学院, 南京 210016; 东南大学数学系, 南京 210096
Keywords:
distance graph;  chromatic number;  combination
距离图;  点色数;  组合
PACS:
O157.5
DOI:
10.3969/j.issn.1003-7985.2003.04.024
Abstract:
An integer distance graph is a graph G(Z, D) with the integer set Z as vertex set, in which an edge joining two vertices u and v if and only if |u-v|∈D, where D is a set of natural numbers.Using a related theorem in combinatorics and some conclusions known to us in the coloring of the distance graph, the chromatic number χ(G) is determined in this paper that is of the distance graph G(Z, D) for some finite distance sets D containing {2, 3} with |D|=4 and containing {2, 3, 5} with |D|=5 by the method in which the combination of a few periodic colorings.
整数距离图是这样一类图G(Z, D), 其中, V(G)=Z, 两点u, v之间存在一条边, 当且仅当|u-v|∈D, 这里D是由自然数组成的一个集合.利用组合数学中的一个相关定理和距离图染色中我们已知的一些结论, 通过几种周期染色组合的方法, 本文确定了|D|=4且D中包含{2, 3}和|D|=5且包含{2, 3, 5}时某些距离图G(Z, D)的点色数χ(D).

References:

[1] Eggleton R B, Erdös P, Skilton D K. Colouring the real line [J]. J Comb Theory Ser B, 1985, 39: 86-100.
[2] Chang G J, Huang L, Zhu X. Circular chromatic numbers and fractional chromatic numbers of distance graphs [J]. Europ J Comb, 1998, 19:423-431.
[3] Voigt M, Walther H. On the chromatic numbers of special distance graphs [J]. Discrete Mathematics, 1991, 97:395-397.
[4] Eggleton R B, Erdös P, Skilton D K. Colouring prime distance graphs [J]. Graphs and Combinatorics, 1990, 6(1): 17-32.
[5] Viogt M, Walther H. Chromatic number of prime distance graphs [J]. Discrete Appl Math, 1994, 51: 197-209.
[6] Huang L, Chang G J. Circular chromatic numbers of distance graphs with distance sets missing multiples [J]. Europ J Comb, 2000, 21: 241-248.
[7] Liu D D F, Zhu X. Distance graphs with missing multiples in the distance sets [J]. J Graph Theory, 1999, 30: 245-259.
[8] Chang G, Liu D, Zhu X. Distance graphs and T-coloring [J]. J Comb Theory Ser B, 1999, 75: 259-269.
[9] Walther H. Über eine spezielle klasse unendlicher graphen [A]. In: Wagner K, Bodendiek R, eds. Graphentheorie [C]. Bibliographisches Institut, Mannhein, 1990.268-295.
[10] Voigt M. Die chromatische zahl einer speziellen klasse unendlicher graphen [D]. Ilmenau: Technical University, 1992.
[11] Margit Voigt. Colouring of distance graphs [J]. ARS Combinatoria, 1999, 52: 3-12.
[12] Kemnitz A, Kolberg H. Colouring of integer distance graphs [J]. Discrete Mathematics, 1998, 191: 113-123.
[13] Frobenius G. Über matrizen aus nichtngativen elementen [M]. Berlin: Sitzungsberichte Preuss Akad Wiss, 1912.456-477.
[14] Zhu X. Circular chromatic number: a survey [J]. Discrete Mathematics, 2001, 229: 371-410.

Memo

Memo:
Biographies: Xu Kexiang(1977—), male, assistant, xukx1005@nuaa.edu.cn; Song Zengmin, male, doctor, professor, zmsong@seu.edu.cn.
Last Update: 2003-12-20