ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 25(1-2) (2005) 151-166
DOI: 10.7151/dmgt.1269


Peter Jacko

Universidad Carlos III de Madrid
Department of Business Administration
Calle Madrid 126, 289 03 Getafe (Madrid), Spain

Stanislav Jendrol'

P.J. Safárik University
Institute of Mathematics
Jesenná 5, 041 54 Košice, Slovakia
e-mail: jendrol@Koš


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: distance coloring, distant chromatic number, hexagonal lattice of the plane, hexagonal tiling, hexagonal grid, radio channel frequency assignment.

2000 Mathematics Subject Classification: 05C15, 05C12.


[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. Safárik University, 2001).
[14] G. Wegner, Graphs with given Diameter and a Colouring Problem (Preprint, University of Dortmund, 1977).

Received 25 November 2003
Revised 22 February 2005