Distance coloring of the hexagonal lattice

Peter Jacko; Stanislav Jendrol'

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 151-166
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Peter Jacko, and Stanislav Jendrol'. "Distance coloring of the hexagonal lattice." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 151-166. <http://eudml.org/doc/270589>.

@article{PeterJacko2005,
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.},
author = {Peter Jacko, Stanislav Jendrol'},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distance coloring; distant chromatic number; hexagonal lattice of the plane; hexagonal tiling; hexagonal grid; radio channel frequency assignment},
language = {eng},
number = {1-2},
pages = {151-166},
title = {Distance coloring of the hexagonal lattice},
url = {http://eudml.org/doc/270589},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Peter Jacko
AU - Stanislav Jendrol'
TI - Distance coloring of the hexagonal lattice
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 151
EP - 166
AB - 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.
LA - eng
KW - distance coloring; distant chromatic number; hexagonal lattice of the plane; hexagonal tiling; hexagonal grid; radio channel frequency assignment
UR - http://eudml.org/doc/270589
ER -

References

top
  1. [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. Zbl0860.05064
  2. [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. Zbl1175.68293
  3. [3] J.P. Georges and D.M. Mauro, Generalized vertex labelings with a condition at distance two, Congr. Numer. 109 (1995) 141-159. Zbl0904.05077
  4. [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. Zbl0767.05080
  5. [5] W.K. Hale, Frequency assignment: theory and applications, Proc. IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899. 
  6. [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 Zbl0930.05087
  7. [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. Zbl1008.05065
  8. [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. Zbl0990.05043
  9. [9] T.R. Jensen and B. Toft, Graph Coloring Problems (John-Wiley & Sons, New York, 1995). Zbl0855.05054
  10. [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. Zbl0194.25201
  11. [11] V.H. MacDonald, The cellular concept, Bell System Technical Journal 58 (1979) 15-41. 
  12. [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. Zbl0924.05024
  13. [13] A. Sevcíková, Distant Chromatic Number of the Planar Graphs (Manuscript, P.J. Šafárik University, 2001). 
  14. [14] G. Wegner, Graphs with given Diameter and a Colouring Problem (Preprint, University of Dortmund, 1977). 

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.