Geodesic
Distance coloring of the hexagonal lattice
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 151-166.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2005_25_1-2_a15,
     author = {Jacko, Peter and Jendrol', Stanislav},
     title = {Distance coloring of the hexagonal lattice},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {151--166},
     publisher = {mathdoc},
     volume = {25},
     number = {1-2},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a15/}
}
TY  - JOUR
AU  - Jacko, Peter
AU  - Jendrol', Stanislav
TI  - Distance coloring of the hexagonal lattice
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 151
EP  - 166
VL  - 25
IS  - 1-2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a15/
LA  - en
ID  - DMGT_2005_25_1-2_a15
ER  - 
%0 Journal Article
%A Jacko, Peter
%A Jendrol', Stanislav
%T Distance coloring of the hexagonal lattice
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 151-166
%V 25
%N 1-2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a15/
%G en
%F DMGT_2005_25_1-2_a15
Jacko, Peter; Jendrol', Stanislav. Distance coloring of the hexagonal lattice. Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 1-2, pp. 151-166. http://geodesic.mathdoc.fr/item/DMGT_2005_25_1-2_a15/

[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:4263::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).