| Title:
|
The $k$-metric colorings of a graph (English) |
| Author:
|
Fujie-Okamoto, Futaba |
| Author:
|
Renzema, Willem |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
137 |
| Issue:
|
1 |
| Year:
|
2012 |
| Pages:
|
45-63 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
detour distance |
| Keyword:
|
metric coloring |
| MSC:
|
05C12 |
| MSC:
|
05C15 |
| MSC:
|
05C78 |
| idZBL:
|
Zbl 1249.05093 |
| idMR:
|
MR2978445 |
| DOI:
|
10.21136/MB.2012.142787 |
| . |
| Date available:
|
2012-04-19T00:00:58Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/142787 |
| . |
| Reference:
|
[1] Chartrand, G., Erwin, D., Harary, F., Zhang, P.: Radio labelings of graphs.Bull. Inst. Combin. Appl. 33 (2001), 77-85. Zbl 0989.05102, MR 1913399 |
| Reference:
|
[2] Chartrand, G., Erwin, D., Zhang, P.: Radio antipodal colorings of graphs.Math. Bohem. 127 (2002), 57-69. Zbl 0995.05056, MR 1895247 |
| Reference:
|
[3] Chartrand, G., Erwin, D., Zhang, P.: A graph labeling problem suggested by FM channel restrictions.Bull. Inst. Combin. Appl. 43 (2005), 43-57. Zbl 1066.05125, MR 2116390 |
| Reference:
|
[4] Chartrand, G., Lesniak, L.: Graphs & Digraphs.Fourth Edition. Chapman & Hall/CRC, Boca Raton, FL (2004). MR 2107429 |
| Reference:
|
[5] Chartrand, G., Nebeský, L., Zhang, P.: Bounds for the Hamiltonian chromatic number of a graph.Congr. Numer. 157 (2002), 113-125. Zbl 1029.05059, MR 1985129 |
| Reference:
|
[6] Chartrand, G., Nebeský, L., Zhang, P.: Radio $k$-colorings of paths.Discuss. Math. Graph Theory 24 (2004), 5-21. Zbl 1056.05053, MR 2118291, 10.7151/dmgt.1209 |
| Reference:
|
[7] Chartrand, G., Nebeský, L., Zhang, P.: Hamiltonian colorings of graphs.Discrete Appl. Math. 146 (2005), 257-272. Zbl 1059.05046, MR 2115148, 10.1016/j.dam.2004.08.007 |
| Reference:
|
[8] Chartrand, G., Nebeský, L., Zhang, P.: On Hamiltonian colorings of graphs.Discrete Math. 290 (2005), 133-143. Zbl 1059.05046, MR 2123385, 10.1016/j.disc.2004.10.009 |
| Reference:
|
[9] Chartrand, G., Zhang, P.: Radio colorings in graphs---a survey.J. Comput. Appl. Math. 2 (2007), 237-252. MR 2563242 |
| Reference:
|
[10] Cozzens, M. B., Roberts, F. S.: $T$-colorings of graphs and the Channel Assignment Problem.Congr. Numer. 35 (1982), 191-208. MR 0725881 |
| Reference:
|
[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. Zbl 0774.05037, MR 1186309 |
| Reference:
|
[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. Zbl 0929.68005, MR 1661872 |
| Reference:
|
[13] Georges, J. P., Mauro, D. W.: Generalized vertex labelings with a condition at distance two.Congr. Numer. 109 (1995), 141-159. Zbl 0904.05077, MR 1369305 |
| Reference:
|
[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. Zbl 0848.05056, MR 1383991, 10.1002/(SICI)1097-0118(199605)22:1<47::AID-JGT7>3.0.CO;2-L |
| Reference:
|
[15] Griggs, J. R., Yeh, R. K.: Labelling graphs with a condition at distance two.SIAM J. Discrete Math. 5 (1992), 586-595. MR 1186826, 10.1137/0405048 |
| Reference:
|
[16] Hale, W.: Frequency assignment: theory and applications.Proc. IEEE 68 (1980), 1497-1514. |
| Reference:
|
[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. Zbl 0941.05023, MR 1723637 |
| Reference:
|
[18] Heuvel, J. van den, Leese, R. A., Shepherd, M. A.: Graph labeling and radio channel assignment.J. Graph Theory 29 (1998), 263-283. MR 1653829, 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V |
| Reference:
|
[19] Khennoufa, R., Togni, O.: A note on radio antipodal colourings of paths.Math. Bohem. 130 (2005), 277-282. Zbl 1110.05033, MR 2164657 |
| Reference:
|
[20] Liu, D., Zhu, X.: Multi-level distance labelings and radio number for paths and cycles.SIAM J. Discrete Math. 3 (2005), 610-621. MR 2191283, 10.1137/S0895480102417768 |
| Reference:
|
[21] Metzger, B. H.: Spectrum management technique.Paper presented at 38th National ORSA Meeting, Detroit, MI (1970). |
| Reference:
|
[22] Nebeský, L.: Hamiltonian colorings of graphs with long cycles.Math. Bohem. 128 (2003), 263-275. Zbl 1050.05055, MR 2012604 |
| Reference:
|
[23] Nebeský, L.: The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs.Czech. Math. J. 56 (2006), 317-338. Zbl 1164.05356, MR 2291739, 10.1007/s10587-006-0020-x |
| Reference:
|
[24] Okamoto, F., Renzema, W. A., Zhang, P.: Results and open problems on Hamiltonian labelings of graphs.Congr. Numer. 198 (2009), 189-206. Zbl 1206.05087, MR 2584352 |
| Reference:
|
[25] Roberts, F.: $T$-colorings of graphs: recent results and open problems.Discrete Math. 93 (1991), 229-245. Zbl 0751.05042, MR 1139583, 10.1016/0012-365X(91)90258-4 |
| Reference:
|
[26] Yeh, R. K.: A survey on labeling graphs with a condition at distance 2.Discrete Math. 306 (2006), 1217-1231. MR 2245647 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[29] Renzema, W. A., Zhang, P.: Hamiltonian labelings of graphs.Involve 2 (2009), 95-114. Zbl 1206.05087, MR 2501348, 10.2140/involve.2009.2.95 |
| Reference:
|
[30] Renzema, W. A., Zhang, P.: On Hamiltonian labelings of graphs.J. Combin. Math. Combin. Comput. 74 (2010), 143-159. Zbl 1225.05158, MR 2675897 |
| . |
