Edge colorings and total colorings of integer distance graphs

Arnfried Kemnitz; Massimiliano Marangio

Discussiones Mathematicae Graph Theory (2002)

  • Volume: 22, Issue: 1, page 149-158
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Arnfried Kemnitz, and Massimiliano Marangio. "Edge colorings and total colorings of integer distance graphs." Discussiones Mathematicae Graph Theory 22.1 (2002): 149-158. <http://eudml.org/doc/270272>.

@article{ArnfriedKemnitz2002,
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.},
author = {Arnfried Kemnitz, Massimiliano Marangio},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {integer distance graph; chromatic number; choice number; chromatic index; choice index; total chromatic number; total choice number},
language = {eng},
number = {1},
pages = {149-158},
title = {Edge colorings and total colorings of integer distance graphs},
url = {http://eudml.org/doc/270272},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Arnfried Kemnitz
AU - Massimiliano Marangio
TI - Edge colorings and total colorings of integer distance graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 1
SP - 149
EP - 158
AB - 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.
LA - eng
KW - integer distance graph; chromatic number; choice number; chromatic index; choice index; total chromatic number; total choice number
UR - http://eudml.org/doc/270272
ER -

References

top
  1. [1] M. Behzad, Graphs and their chromatic numbers (Doct. Thesis, Michigan State University, 1965). 
  2. [2] B. Bollobás and A.J. Harris, List-colourings of graphs, Graphs and Combinatorics 1 (1985) 115-127, doi: 10.1007/BF02582936. Zbl0606.05027
  3. [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. Zbl0876.05032
  4. [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 Zbl0878.05028
  5. [5] R.B. Eggleton, Three unsolved problems in graph theory, Ars Combin. 23A (1987) 105-121. Zbl0634.05062
  6. [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. Zbl0549.05029
  7. [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. Zbl0698.05033
  8. [8] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congressus Numerantium 26 (1979) 125-157. 
  9. [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. Zbl0826.05026
  10. [10] A. Hackmann and A. Kemnitz, List edge colorings of outerplanar graphs, Ars Combin. (to appear). 
  11. [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). Zbl0880.05035
  12. [12] A.J. Harris, Problems and conjectures in extremal graph theory (Ph.D. Dissertation, Cambridge Univerity, 1985). 
  13. [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. Zbl0785.05035
  14. [14] T.R. Jensen and Bjarne Toft, Graph coloring problems (Wiley, New York, 1995). Zbl0855.05054
  15. [15] M. Juvan and B. Mohar, List colorings of outerplanar graphs (Manuscript, 1998). Zbl0957.05044
  16. [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. Zbl0911.05033
  17. [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. Zbl0956.05044
  18. [18] A. Kemnitz and M. Marangio, Chromatic numbers of integer distance graphs, Discrete Math. (to appear). Zbl0988.05039
  19. [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. Zbl0871.05023
  20. [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 Zbl0922.05025
  21. [21] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analiz. 3 (1964) 25-30 (Russian). 
  22. [22] M. Voigt, Colouring of distance graphs, Ars Combin. 52 (1999) 3-12. Zbl0977.05047
  23. [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. Zbl0808.05051
  24. [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. [25] X. Zhu, Distance graphs on the real line (Manuscript, 1996). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.