Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2002 | 22 | 1 | 149-158
Tytuł artykułu

Edge colorings and total colorings of integer distance graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
Opis fizyczny
  • Diskrete Mathematik, Technische Universität Braunschweig, Pockelsstr. 14, D-38106 Braunschweig, Germany
  • Diskrete Mathematik, Technische Universität Braunschweig, Pockelsstr. 14, D-38106 Braunschweig, Germany
  • [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).
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.