Edge colorings and total colorings of integer distance graphs
Arnfried Kemnitz ; Massimiliano Marangio
Discussiones Mathematicae Graph Theory, Tome 22 (2002), p. 149-158 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2002-01-01
EUDML-ID : urn:eudml:doc:270272 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1164,
     author = {Arnfried Kemnitz and Massimiliano Marangio},
     title = {Edge colorings and total colorings of integer distance graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {22},
     year = {2002},
     pages = {149-158},
     zbl = {1010.05025},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1164}
}

Arnfried Kemnitz; Massimiliano Marangio. Edge colorings and total colorings of integer distance graphs. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 149-158. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1164/

[000] [1] M. Behzad, Graphs and their chromatic numbers (Doct. Thesis, Michigan State University, 1965).

[001] [2] B. Bollobás and A.J. Harris, List-colourings of graphs, Graphs and Combinatorics 1 (1985) 115-127, doi: 10.1007/BF02582936. | Zbl 0606.05027

[002] [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. | Zbl 0876.05032

[003] [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 | Zbl 0878.05028

[004] [5] R.B. Eggleton, Three unsolved problems in graph theory, Ars Combin. 23A (1987) 105-121. | Zbl 0634.05062

[005] [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. | Zbl 0549.05029

[006] [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. | Zbl 0698.05033

[007] [8] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congressus Numerantium 26 (1979) 125-157.

[008] [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. | Zbl 0826.05026

[009] [10] A. Hackmann and A. Kemnitz, List edge colorings of outerplanar graphs, Ars Combin. (to appear).

[010] [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). | Zbl 0880.05035

[011] [12] A.J. Harris, Problems and conjectures in extremal graph theory (Ph.D. Dissertation, Cambridge Univerity, 1985).

[012] [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. | Zbl 0785.05035

[013] [14] T.R. Jensen and Bjarne Toft, Graph coloring problems (Wiley, New York, 1995). | Zbl 0855.05054

[014] [15] M. Juvan and B. Mohar, List colorings of outerplanar graphs (Manuscript, 1998). | Zbl 0957.05044

[015] [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. | Zbl 0911.05033

[016] [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. | Zbl 0956.05044

[017] [18] A. Kemnitz and M. Marangio, Chromatic numbers of integer distance graphs, Discrete Math. (to appear). | Zbl 0988.05039

[018] [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. | Zbl 0871.05023

[019] [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 | Zbl 0922.05025

[020] [21] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analiz. 3 (1964) 25-30 (Russian).

[021] [22] M. Voigt, Colouring of distance graphs, Ars Combin. 52 (1999) 3-12. | Zbl 0977.05047

[022] [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. | Zbl 0808.05051

[023] [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).

[024] [25] X. Zhu, Distance graphs on the real line (Manuscript, 1996).