The $k$-metric colorings of a graph

Fujie-Okamoto, Futaba ; Renzema, Willem ; Zhang, Ping

Mathematica Bohemica, Tome 137 (2012) no. 1, pp. 45-63

Abstract (VO)

For a nontrivial connected graph $G$ of order $n$, the detour distance $D(u,v)$ between two vertices $u$ and $v$ in $G$ is the length of a longest $u-v$ path in $G$. Detour distance is a metric on the vertex set of $G$. For each integer $k$ with $1\le k\le n-1$, a coloring $c\colon V(G)\to \mathbb N$ is a $k$-metric coloring of $G$ if $|c(u)-c(v)|+D(u,v)\ge k+1$ for every two distinct vertices $u$ and $v$ of $G$. The value $\chi _m^k(c)$ of a $k$-metric coloring $c$ is the maximum color assigned by $c$ to a vertex of $G$ and the $k$-metric chromatic number $\chi _m^k(G)$ of $G$ is the minimum value of a $k$-metric coloring of $G$. For every nontrivial connected graph $G$ of order $n$, $\chi _m^1(G)\le \chi _m^2(G)\le \cdots \le \chi _m^{n-1}(G)$. Metric chromatic numbers provide a generalization of several well-studied coloring parameters in graphs. Upper and lower bounds have been established for $\chi _m^k(G)$ in terms of other graphical parameters of a graph $G$ and exact values of $k$-metric chromatic numbers have been determined for complete multipartite graphs and cycles. For a nontrivial connected graph $G$, the anti-diameter ${\rm adiam}(G)$ is the minimum detour distance between two vertices of $G$. We show that the ${\rm adiam}(G)$-metric chromatic number of a graph $G$ provides information on the Hamiltonian properties of the graph and investigate realization results and problems on this parameter.

Détail

DOI : 10.21136/MB.2012.142787

Classification : 05C12, 05C15, 05C78
Keywords: detour distance; metric coloring

Bibliographie

[1] Chartrand, G., Erwin, D., Harary, F., Zhang, P.: Radio labelings of graphs. Bull. Inst. Combin. Appl. 33 (2001), 77-85. | MR | Zbl

[2] Chartrand, G., Erwin, D., Zhang, P.: Radio antipodal colorings of graphs. Math. Bohem. 127 (2002), 57-69. | MR | Zbl

[3] Chartrand, G., Erwin, D., Zhang, P.: A graph labeling problem suggested by FM channel restrictions. Bull. Inst. Combin. Appl. 43 (2005), 43-57. | MR | Zbl

[4] Chartrand, G., Lesniak, L.: Graphs & Digraphs. Fourth Edition. Chapman & Hall/CRC, Boca Raton, FL (2004). | MR

[5] Chartrand, G., Nebeský, L., Zhang, P.: Bounds for the Hamiltonian chromatic number of a graph. Congr. Numer. 157 (2002), 113-125. | MR | Zbl

[6] Chartrand, G., Nebeský, L., Zhang, P.: Radio $k$-colorings of paths. Discuss. Math. Graph Theory 24 (2004), 5-21. | DOI | MR | Zbl

[7] Chartrand, G., Nebeský, L., Zhang, P.: Hamiltonian colorings of graphs. Discrete Appl. Math. 146 (2005), 257-272. | DOI | MR | Zbl

[8] Chartrand, G., Nebeský, L., Zhang, P.: On Hamiltonian colorings of graphs. Discrete Math. 290 (2005), 133-143. | DOI | MR | Zbl

[9] Chartrand, G., Zhang, P.: Radio colorings in graphs---a survey. J. Comput. Appl. Math. 2 (2007), 237-252. | MR

[10] Cozzens, M. B., Roberts, F. S.: $T$-colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982), 191-208. | MR

[11] Cozzens, M. B., Roberts, F. S.: Greedy algorithms for ${T}$-colorings of complete graphs and the meaningfulness of conclusions about them. J. Combin. Inform. System Sci. 16 (1991), 286-299. | MR | Zbl

[12] Fotakis, D., Pantziou, G., Pentaris, G., Spirakis, P.: Frequency assignment in mobile and radio networks. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 45 (1999), 73-90. | MR | Zbl

[13] Georges, J. P., Mauro, D. W.: Generalized vertex labelings with a condition at distance two. Congr. Numer. 109 (1995), 141-159. | MR | Zbl

[14] Georges, J. P., Mauro, D. W.: On the size of graphs labeled with a condition at distance two. J. Graph Theory 22 (1996), 47-57. | DOI | MR | Zbl

[15] Griggs, J. R., Yeh, R. K.: Labelling graphs with a condition at distance two. SIAM J. Discrete Math. 5 (1992), 586-595. | DOI | MR

[16] Hale, W.: Frequency assignment: theory and applications. Proc. IEEE 68 (1980), 1497-1514.

[17] Harary, F., Plantholt, M.: Graphs whose radio coloring number equals the number of nodes. Centre de Recherches Mathématiques. CRM Proceedings and Lecture Notes 23 (1999), 99-100. | MR | Zbl

[18] Heuvel, J. van den, Leese, R. A., Shepherd, M. A.: Graph labeling and radio channel assignment. J. Graph Theory 29 (1998), 263-283. | DOI | MR

[19] Khennoufa, R., Togni, O.: A note on radio antipodal colourings of paths. Math. Bohem. 130 (2005), 277-282. | MR | Zbl

[20] Liu, D., Zhu, X.: Multi-level distance labelings and radio number for paths and cycles. SIAM J. Discrete Math. 3 (2005), 610-621. | DOI | MR

[21] Metzger, B. H.: Spectrum management technique. Paper presented at 38th National ORSA Meeting, Detroit, MI (1970).

[22] Nebeský, L.: Hamiltonian colorings of graphs with long cycles. Math. Bohem. 128 (2003), 263-275. | MR | Zbl

[23] Nebeský, L.: The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs. Czech. Math. J. 56 (2006), 317-338. | DOI | MR | Zbl

[24] Okamoto, F., Renzema, W. A., Zhang, P.: Results and open problems on Hamiltonian labelings of graphs. Congr. Numer. 198 (2009), 189-206. | MR | Zbl

[25] Roberts, F.: $T$-colorings of graphs: recent results and open problems. Discrete Math. 93 (1991), 229-245. | DOI | MR | Zbl

[26] Yeh, R. K.: A survey on labeling graphs with a condition at distance 2. Discrete Math. 306 (2006), 1217-1231. | MR

[27] Walsh, T. R.: The number of edge 3-colorings of the $n$-prism. Centre de Recherches Mathématiques. CRM proceedings and Lecture Notes 23 (1999), 127-129. | MR

[28] Walsh, T. R.: The cost of radio-colorings of paths and cycles. Centre de Recherches Mathématiques. CRM proceedings and Lecture Notes 23 (1999), 131-133. | MR

[29] Renzema, W. A., Zhang, P.: Hamiltonian labelings of graphs. Involve 2 (2009), 95-114. | DOI | MR | Zbl

[30] Renzema, W. A., Zhang, P.: On Hamiltonian labelings of graphs. J. Combin. Math. Combin. Comput. 74 (2010), 143-159. | MR | Zbl