Download PDF - Distance coloring of the hexagonal latticeAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Distance coloring of the hexagonal lattice

Authors 1, 2

Affiliations

  1. Universidad Carlos III de Madrid, Department of Business Administration, Calle Madrid 126, 289 03 Getafe (Madrid), Spain
  2. P.J. Šafárik University, Institute of Mathematics, Jesenná 5, 041 54 Košice, Slovakia

Abstract

Motivated by the frequency assignment problem we study the d-distant coloring of the vertices of an infinite plane hexagonal lattice H. Let d be a positive integer. A d-distant coloring of the lattice H is a coloring of the vertices of H such that each pair of vertices distance at most d apart have different colors. The d-distant chromatic number of H, denoted χd(H), is the minimum number of colors needed for a d-distant coloring of H. We give the exact value of χd(H) for any d odd and estimations for any d even.

Keywords

ENG
distance coloring, distant chromatic number, hexagonal lattice of the plane, hexagonal tiling, hexagonal grid, radio channel frequency assignment

Bibliography

  1. G.J. Chang and D. Kuo, The L(2,1)-labeling problem on graphs, SIAM J. Discrete Math. 9 (1996) 309-316, doi: 10.1137/S0895480193245339.
  2. G. Fertin, E. Godard and A. Raspaud, Acyclic and k-distance coloring of the grid, Information Processing Letters 87 (2003) 51-58, doi: 10.1016/S0020-0190(03)00232-1.
  3. J.P. Georges and D.M. Mauro, Generalized vertex labelings with a condition at distance two, Congr. Numer. 109 (1995) 141-159.
  4. J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586-595, doi: 10.1137/0405048.
  5. W.K. Hale, Frequency assignment: theory and applications, Proc. IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899.
  6. J. van den Heuvel, R.A. Leese and M.A. Shepherd, Graph labeling and radio Channel assignment, J. Graph Theory 29 (1998) 263-283, doi: 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V
  7. J. van den Heuvel and S. McGuinness, Coloring the square of a planar graph, J. Graph Theory 42 (2003) 110-124, doi: 10.1002/jgt.10077.
  8. S. Jendrol' and Z. Skupień, Local structures in plane maps and distance colourings, Discrete Math. 236 (2001) 167-177, doi: 10.1016/S0012-365X(00)00440-4.
  9. T.R. Jensen and B. Toft, Graph Coloring Problems (John-Wiley & Sons, New York, 1995).
  10. F. Kramer and H. Kramer, Ein farbungsproblem der knotenpunkte eines graphen bezuglich der distanz, P. Rev. Roumaine Math. Pures Appl. 14 (1969) 1031-1038.
  11. V.H. MacDonald, The cellular concept, Bell System Technical Journal 58 (1979) 15-41.
  12. C. McDiarmid and B. Reed, Colouring proximity graphs in the plane, Discrete Math. 199 (1999) 123-137, doi: 10.1016/S0012-365X(98)00292-1.
  13. A. Sevcíková, Distant Chromatic Number of the Planar Graphs (Manuscript, P.J. Šafárik University, 2001).
  14. G. Wegner, Graphs with given Diameter and a Colouring Problem (Preprint, University of Dortmund, 1977).
Discussiones Mathematicae Graph Theory
2005/25/1-2
Export to PBN, Opens in new tab
Pages:
151-166
Main language of publication
English
Received
2003-11-25
Accepted
2005-02-22
Published
2005

DOI: 10.7151/dmgt.1269

Exact and natural sciences