Geodesic
Edge colorings and total colorings of integer distance graphs
Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 1, pp. 149-158.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2002_22_1_a11,
     author = {Kemnitz, Arnfried and Marangio, Massimiliano},
     title = {Edge colorings and total colorings of integer distance graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {149--158},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a11/}
}
TY  - JOUR
AU  - Kemnitz, Arnfried
AU  - Marangio, Massimiliano
TI  - Edge colorings and total colorings of integer distance graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2002
SP  - 149
EP  - 158
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a11/
LA  - en
ID  - DMGT_2002_22_1_a11
ER  - 
%0 Journal Article
%A Kemnitz, Arnfried
%A Marangio, Massimiliano
%T Edge colorings and total colorings of integer distance graphs
%J Discussiones Mathematicae. Graph Theory
%D 2002
%P 149-158
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a11/
%G en
%F DMGT_2002_22_1_a11
Kemnitz, Arnfried; Marangio, Massimiliano. Edge colorings and total colorings of integer distance graphs. Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 1, pp. 149-158. http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a11/

[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:4287::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:167::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).