PDF

Discussiones Mathematicae Graph Theory 22(1) (2002) 149-158
DOI: https://doi.org/10.7151/dmgt.1164

EDGE COLORINGS AND TOTAL COLORINGS OF INTEGER DISTANCE GRAPHS

Arnfried Kemnitz and Massimiliano Marangio

Diskrete Mathematik
Technische Universität Braunschweig
Pockelsstr. 14, D-38106 Braunschweig, Germany
e-mail: a.kemnitz@tu-bs.de
e-mail: m.marangio@tu-bs.de

Dedicated to Hansjoachim Walther on the occasion of his sixtieth birthday.

Abstract

An integer distance graph is a graph G(D) with the set Z of integers as vertex set and two vertices u,v ∈ Z are adjacent if and only if |u−v| ∈ D where the distance set D is a subset of the positive integers N. In this note we determine the chromatic index, the choice index, the total chromatic number and the total choice number of all integer distance graphs, and the choice number of special integer distance graphs.

Keywords: integer distance graph, chromatic number, choice number, chromatic index, choice index, total chromatic number, total choice number.

2000 Mathematics Subject Classification: 05C15.

References

[1]	M. Behzad, Graphs and their chromatic numbers (Doct. Thesis, Michigan State University, 1965).
[2]	B. Bollobás and A.J. Harris, List-colourings of graphs, Graphs and Combinatorics 1 (1985) 115-127, doi: 10.1007/BF02582936.
[3]	O.V. Borodin, A.V. Kostochka, and D.R. Woodall, List edge and list total colourings of multigraphs, J. Combin. Theory (B) 71 (1997) 184-204, doi: 10.1006/jctb.1997.1780.
[4]	G.J. Chang, J.-J. Chen, and K.-Ch. Huang, Integral distance graphs, J. Graph Theory 25 (1997) 287-294, doi: 10.1002/(SICI)1097-0118(199708)25:4<287::AID-JGT6>3.0.CO;2-G.
[5]	R.B. Eggleton, Three unsolved problems in graph theory, Ars Combin. 23A (1987) 105-121.
[6]	R.B. Eggleton, P. Erdős and D.K. Skilton, Colouring the real line, J. Combin. Theory (B) 39 (1985) 86-100, Erratum: 41 (1986), 139.
[7]	R.B. Eggleton, P. Erdős and D.K. Skilton, Colouring prime distance graphs, Graphs and Combinatorics 6 (1990) 17-32, doi: 10.1007/BF01787476.
[8]	P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congressus Numerantium 26 (1979) 125-157.
[9]	F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory (B) 63 (1995) 153-158, doi: 10.1006/jctb.1995.1011.
[10]	A. Hackmann and A. Kemnitz, List edge colorings of outerplanar graphs, Ars Combin. (to appear).
[11]	R. Häggkvist and J.C.M. Janssen, New bounds on the list-chromatic index of the complete graph and other simple graphs, Research report 19, Department of Mathematics (University of Ulmeå, 1993).
[12]	A.J. Harris, Problems and conjectures in extremal graph theory (Ph.D. Dissertation, Cambridge Univerity, 1985).
[13]	A.J.W. Hilton and H.R. Hind, Total chromatic number of graphs having large maximum degree, Discrete Math. 117 (1993) 127-140, doi: 10.1016/0012-365X(93)90329-R.
[14]	T.R. Jensen and Bjarne Toft, Graph coloring problems (Wiley, New York, 1995).
[15]	M. Juvan and B. Mohar, List colorings of outerplanar graphs (Manuscript, 1998).
[16]	M. Juvan, B. Mohar and R. Skrekovski, List-total colourings of graphs, Combinatorics, Probability and Computing 7 (1998) 181-188, doi: 10.1017/S0963548397003210.
[17]	A. Kemnitz and H. Kolberg, Coloring of integer distance graphs, Discrete Math. 191 (1998) 113-123, doi: 10.1016/S0012-365X(98)00099-5.
[18]	A. Kemnitz and M. Marangio, Chromatic numbers of integer distance graphs, Discrete Math. (to appear).
[19]	A.V. Kostochka, The total chromatic number of any multigraph with maximum degree five is at most seven, Discrete Math. 162 (1996) 199-214, doi: 10.1016/0012-365X(95)00286-6.
[20]	D.P. Sanders and Y. Zhao, On total 9-coloring planar graphs of maximum degree seven, J. Graph Theory 31 (1999) 67-73, doi: 10.1002/(SICI)1097-0118(199905)31:1<67::AID-JGT6>3.0.CO;2-C.
[21]	V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analiz. 3 (1964) 25-30 (Russian).
[22]	M. Voigt, Colouring of distance graphs, Ars Combin. 52 (1999) 3-12.
[23]	M. Voigt and H. Walther, Chromatic number of prime distance graphs, Discrete Appl. Math. 51 (1994) 197-209, doi: 10.1016/0166-218X(94)90109-0.
[24]	H. Walther, Über eine spezielle Klasse unendlicher Graphen, Graphentheorie II (Klaus Wagner and Rainer Bodendiek, eds.), Bibliographisches Institut Wissenschaftsverlag, 1990, pp. 268-295 (German).
[25]	X. Zhu, Distance graphs on the real line (Manuscript, 1996).

Received 22 July 2000
Revised 30 January 2001