# 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

## Access Full Article

top## Abstract

top## How to cite

topPeter 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] 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] 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] 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] 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] 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 Zbl0930.05087
- [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] 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] T.R. Jensen and B. Toft, Graph Coloring Problems (John-Wiley & Sons, New York, 1995). Zbl0855.05054
- [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] 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. Zbl0924.05024
- [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).

## NotesEmbed ?

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