[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 Kexiang¹;  Song Zengmin²

¹College of Sciences, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
²Department of Mathematics, Southeast University, Nanjing 210096, China

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.

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.

Common functions