The k -metric colorings of a graph

Futaba Fujie-Okamoto; Willem Renzema; Ping Zhang

Mathematica Bohemica (2012)

  • Volume: 137, Issue: 1, page 45-63
  • ISSN: 0862-7959

Abstract

top
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 ≤ k ≤ n - 1 , a coloring c : V ( G ) → ℕ is a k -metric coloring of G if | c ( u ) - c ( v ) | + D ( u , v ) ≥ k + 1 for every two distinct vertices u and v of G . The value χ 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 χ 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 , χ m 1 ( G ) ≤ χ m 2 ( G ) ≤ ⋯ ≤ χ 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 χ 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 adiam ( G ) is the minimum detour distance between two vertices of G . We show that the 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.

How to cite

top

Fujie-Okamoto, Futaba, Renzema, Willem, and Zhang, Ping. "The $k$-metric colorings of a graph." Mathematica Bohemica 137.1 (2012): 45-63. <http://eudml.org/doc/246364>.

@article{Fujie2012,
abstract = {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)\rightarrow \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.},
author = {Fujie-Okamoto, Futaba, Renzema, Willem, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {detour distance; metric coloring; detour distance; metric coloring; metric chromatic number},
language = {eng},
number = {1},
pages = {45-63},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The $k$-metric colorings of a graph},
url = {http://eudml.org/doc/246364},
volume = {137},
year = {2012},
}

TY - JOUR
AU - Fujie-Okamoto, Futaba
AU - Renzema, Willem
AU - Zhang, Ping
TI - The $k$-metric colorings of a graph
JO - Mathematica Bohemica
PY - 2012
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 137
IS - 1
SP - 45
EP - 63
AB - 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)\rightarrow \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.
LA - eng
KW - detour distance; metric coloring; detour distance; metric coloring; metric chromatic number
UR - http://eudml.org/doc/246364
ER -

References

top
  1. Chartrand, G., Erwin, D., Harary, F., Zhang, P., Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001), 77-85. (2001) Zbl0989.05102MR1913399
  2. Chartrand, G., Erwin, D., Zhang, P., Radio antipodal colorings of graphs, Math. Bohem. 127 (2002), 57-69. (2002) Zbl0995.05056MR1895247
  3. Chartrand, G., Erwin, D., Zhang, P., A graph labeling problem suggested by FM channel restrictions, Bull. Inst. Combin. Appl. 43 (2005), 43-57. (2005) Zbl1066.05125MR2116390
  4. Chartrand, G., Lesniak, L., Graphs & Digraphs, Fourth Edition. Chapman & Hall/CRC, Boca Raton, FL (2004). (2004) MR2107429
  5. Chartrand, G., Nebeský, L., Zhang, P., Bounds for the Hamiltonian chromatic number of a graph, Congr. Numer. 157 (2002), 113-125. (2002) Zbl1029.05059MR1985129
  6. Chartrand, G., Nebeský, L., Zhang, P., 10.7151/dmgt.1209, Discuss. Math. Graph Theory 24 (2004), 5-21. (2004) Zbl1056.05053MR2118291DOI10.7151/dmgt.1209
  7. Chartrand, G., Nebeský, L., Zhang, P., 10.1016/j.dam.2004.08.007, Discrete Appl. Math. 146 (2005), 257-272. (2005) Zbl1059.05046MR2115148DOI10.1016/j.dam.2004.08.007
  8. Chartrand, G., Nebeský, L., Zhang, P., 10.1016/j.disc.2004.10.009, Discrete Math. 290 (2005), 133-143. (2005) Zbl1059.05046MR2123385DOI10.1016/j.disc.2004.10.009
  9. Chartrand, G., Zhang, P., Radio colorings in graphs---a survey, J. Comput. Appl. Math. 2 (2007), 237-252. (2007) MR2563242
  10. Cozzens, M. B., Roberts, F. S., T -colorings of graphs and the Channel Assignment Problem, Congr. Numer. 35 (1982), 191-208. (1982) MR0725881
  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. (1991) Zbl0774.05037MR1186309
  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. (1999) Zbl0929.68005MR1661872
  13. Georges, J. P., Mauro, D. W., Generalized vertex labelings with a condition at distance two, Congr. Numer. 109 (1995), 141-159. (1995) Zbl0904.05077MR1369305
  14. Georges, J. P., Mauro, D. W., 10.1002/(SICI)1097-0118(199605)22:1<47::AID-JGT7>3.0.CO;2-L, J. Graph Theory 22 (1996), 47-57. (1996) Zbl0848.05056MR1383991DOI10.1002/(SICI)1097-0118(199605)22:1<47::AID-JGT7>3.0.CO;2-L
  15. Griggs, J. R., Yeh, R. K., 10.1137/0405048, SIAM J. Discrete Math. 5 (1992), 586-595. (1992) MR1186826DOI10.1137/0405048
  16. Hale, W., Frequency assignment: theory and applications, Proc. IEEE 68 (1980), 1497-1514. (1980) 
  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. (1999) Zbl0941.05023MR1723637
  18. Heuvel, J. van den, Leese, R. A., Shepherd, M. A., 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V, J. Graph Theory 29 (1998), 263-283. (1998) MR1653829DOI10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V
  19. Khennoufa, R., Togni, O., A note on radio antipodal colourings of paths, Math. Bohem. 130 (2005), 277-282. (2005) Zbl1110.05033MR2164657
  20. Liu, D., Zhu, X., 10.1137/S0895480102417768, SIAM J. Discrete Math. 3 (2005), 610-621. (2005) MR2191283DOI10.1137/S0895480102417768
  21. Metzger, B. H., Spectrum management technique, Paper presented at 38th National ORSA Meeting, Detroit, MI (1970). (1970) 
  22. Nebeský, L., Hamiltonian colorings of graphs with long cycles, Math. Bohem. 128 (2003), 263-275. (2003) Zbl1050.05055MR2012604
  23. Nebeský, L., 10.1007/s10587-006-0020-x, Czech. Math. J. 56 (2006), 317-338. (2006) Zbl1164.05356MR2291739DOI10.1007/s10587-006-0020-x
  24. Okamoto, F., Renzema, W. A., Zhang, P., Results and open problems on Hamiltonian labelings of graphs, Congr. Numer. 198 (2009), 189-206. (2009) Zbl1206.05087MR2584352
  25. Roberts, F., 10.1016/0012-365X(91)90258-4, Discrete Math. 93 (1991), 229-245. (1991) Zbl0751.05042MR1139583DOI10.1016/0012-365X(91)90258-4
  26. Yeh, R. K., A survey on labeling graphs with a condition at distance 2, Discrete Math. 306 (2006), 1217-1231. (2006) MR2245647
  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. (1999) MR1723640
  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. (1999) MR1723641
  29. Renzema, W. A., Zhang, P., 10.2140/involve.2009.2.95, Involve 2 (2009), 95-114. (2009) Zbl1206.05087MR2501348DOI10.2140/involve.2009.2.95
  30. Renzema, W. A., Zhang, P., On Hamiltonian labelings of graphs, J. Combin. Math. Combin. Comput. 74 (2010), 143-159. (2010) Zbl1225.05158MR2675897

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.