Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
detour distance; metric coloring
detour distance; metric coloring
Summary:
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.
References:
[1] Chartrand, G., Erwin, D., Harary, F., Zhang, P.: Radio labelings of graphs. Bull. Inst. Combin. Appl. 33 (2001), 77-85. MR 1913399 | Zbl 0989.05102
[2] Chartrand, G., Erwin, D., Zhang, P.: Radio antipodal colorings of graphs. Math. Bohem. 127 (2002), 57-69. MR 1895247 | Zbl 0995.05056
[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 2116390 | Zbl 1066.05125
[4] Chartrand, G., Lesniak, L.: Graphs & Digraphs. Fourth Edition. Chapman & Hall/CRC, Boca Raton, FL (2004). MR 2107429
[5] Chartrand, G., Nebeský, L., Zhang, P.: Bounds for the Hamiltonian chromatic number of a graph. Congr. Numer. 157 (2002), 113-125. MR 1985129 | Zbl 1029.05059
[6] Chartrand, G., Nebeský, L., Zhang, P.: Radio $k$-colorings of paths. Discuss. Math. Graph Theory 24 (2004), 5-21. DOI 10.7151/dmgt.1209 | MR 2118291 | Zbl 1056.05053
[7] Chartrand, G., Nebeský, L., Zhang, P.: Hamiltonian colorings of graphs. Discrete Appl. Math. 146 (2005), 257-272. DOI 10.1016/j.dam.2004.08.007 | MR 2115148 | Zbl 1059.05046
[8] Chartrand, G., Nebeský, L., Zhang, P.: On Hamiltonian colorings of graphs. Discrete Math. 290 (2005), 133-143. DOI 10.1016/j.disc.2004.10.009 | MR 2123385 | Zbl 1059.05046
[9] Chartrand, G., Zhang, P.: Radio colorings in graphs---a survey. J. Comput. Appl. Math. 2 (2007), 237-252. MR 2563242
[10] Cozzens, M. B., Roberts, F. S.: $T$-colorings of graphs and the Channel Assignment Problem. Congr. Numer. 35 (1982), 191-208. MR 0725881
[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 1186309 | Zbl 0774.05037
[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 1661872 | Zbl 0929.68005
[13] Georges, J. P., Mauro, D. W.: Generalized vertex labelings with a condition at distance two. Congr. Numer. 109 (1995), 141-159. MR 1369305 | Zbl 0904.05077
[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 10.1002/(SICI)1097-0118(199605)22:1<47::AID-JGT7>3.0.CO;2-L | MR 1383991 | Zbl 0848.05056
[15] Griggs, J. R., Yeh, R. K.: Labelling graphs with a condition at distance two. SIAM J. Discrete Math. 5 (1992), 586-595. DOI 10.1137/0405048 | MR 1186826
[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 1723637 | Zbl 0941.05023
[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 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V | MR 1653829
[19] Khennoufa, R., Togni, O.: A note on radio antipodal colourings of paths. Math. Bohem. 130 (2005), 277-282. MR 2164657 | Zbl 1110.05033
[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 10.1137/S0895480102417768 | MR 2191283
[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 2012604 | Zbl 1050.05055
[23] Nebeský, L.: The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs. Czech. Math. J. 56 (2006), 317-338. DOI 10.1007/s10587-006-0020-x | MR 2291739 | Zbl 1164.05356
[24] Okamoto, F., Renzema, W. A., Zhang, P.: Results and open problems on Hamiltonian labelings of graphs. Congr. Numer. 198 (2009), 189-206. MR 2584352 | Zbl 1206.05087
[25] Roberts, F.: $T$-colorings of graphs: recent results and open problems. Discrete Math. 93 (1991), 229-245. DOI 10.1016/0012-365X(91)90258-4 | MR 1139583 | Zbl 0751.05042
[26] Yeh, R. K.: A survey on labeling graphs with a condition at distance 2. Discrete Math. 306 (2006), 1217-1231. MR 2245647
[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 1723640
[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 1723641
[29] Renzema, W. A., Zhang, P.: Hamiltonian labelings of graphs. Involve 2 (2009), 95-114. DOI 10.2140/involve.2009.2.95 | MR 2501348 | Zbl 1206.05087
[30] Renzema, W. A., Zhang, P.: On Hamiltonian labelings of graphs. J. Combin. Math. Combin. Comput. 74 (2010), 143-159. MR 2675897 | Zbl 1225.05158
Search
Partner of
