×

\([r,s,t]\)-colorings of graph products. (English) Zbl 1298.05113

Summary: Let \(G=(V,E)\) be a graph with vertex set \(V\) and edge set \(E\). Given non negative integers \(r\), \(s\) and \(t\), an \([r,s,t]\)-coloring of a graph \(G\) is a proper total coloring where the neighboring elements of \(G\) (vertices and edges) receive colors with a certain difference \(r\) between colors of adjacent vertices, a difference \(s\) between colors of adjacent edges and a difference \(t\) between colors of a vertex and an incident edge. Thus \([r,s,t]\)-colorings generalize the classical colorings of graphs and can have applications in different fields like scheduling, channel assignment problem, etc. The \([r,s,t]\)-chromatic number \(\chi_{r,s,t}(G)\) of \(G\) is the minimum \(k\) such that \(G\) admits an \([r,s,t]\)-coloring. In our paper we propose several bounds for the \([r,s,t]\)-chromatic number of the Cartesian and direct products of some graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C76 Graph operations (line graphs, products, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bazzaro F., Montassier M., Raspaud A.: (d,1)-total labelling of planar graphs with large girth and high maximum degree. Discrete Math. 307, 2141-2151 (2007) · Zbl 1120.05076 · doi:10.1016/j.disc.2005.12.059
[2] Bottreau A., Métivier Y.: Some remarks on the Kronecker product of graphs. Inf. Process. Lett. 68, 55-61 (1998) · Zbl 1339.05338 · doi:10.1016/S0020-0190(98)00145-8
[3] Chang C.Y., Clark W.E., Hare E.O.: Domination numbers of complete grid graphs I. Ars Combinatoria 36, 97-111 (1994) · Zbl 0818.05038
[4] Čižek N., Klavžar S.: On the chromatic number of the lexicographic product and the cartesian sum of graphs. Discrete Math. 134(1-3), 17-24 (1994) · Zbl 0815.05030
[5] Dekar L., Effantin B., Kheddouci H.: [r, s, t]-colorings of Trees and Bipartite graphs. Discrete Math. 310, 260-269 (2010) · Zbl 1215.05060 · doi:10.1016/j.disc.2008.09.021
[6] Effantin B., Kheddouci H.: Grundy number of graphs. Discussiones Mathematicae Graph Theory 27(1), 5-18 (2007) · Zbl 1133.05031 · doi:10.7151/dmgt.1339
[7] Gravier S.: Total domination number of grid graphs. Discrete Appl. Math. 121(1-3), 119-128 (2002) · Zbl 0995.05109 · doi:10.1016/S0166-218X(01)00297-9
[8] Horton J.D., Wallis W.D.: Factoring the cartesian product of a cubic graph and a triangle. Discrete Math. 259(1-3), 137-146 (2002) · Zbl 1008.05120 · doi:10.1016/S0012-365X(02)00376-X
[9] Jha P.K., Agnihotri N., Kumar R.: Long cycles and long paths in the Kronecker product of a cycle and a tree. Discrete Appl. Math. 74, 101-121 (1997) · Zbl 0872.05026 · doi:10.1016/S0166-218X(96)00022-4
[10] Jha P.K.: Kronecker product of paths and cycles: decomposition, factorization and bi-pancyclicity. Discrete Math. 182, 153-167 (1998) · Zbl 0890.05052 · doi:10.1016/S0012-365X(97)00138-6
[11] Jha P.K.: Smallest independent dominating sets in Kronecker product of cycles. Discrete Appl. Math. 113, 303-306 (2001) · Zbl 0991.05083 · doi:10.1016/S0166-218X(00)00295-X
[12] Jha P.K.: Perfect r-domination in the Kronecker product of two cycles, with an application to diagonal/toroidal mesh. Inf. Process. Lett. 87, 163-168 (2003) · Zbl 1161.68678 · doi:10.1016/S0020-0190(03)00268-0
[13] Kemnitz A., Marangio M.: [r, s, t]-colorings of graphs. Discrete Math. 307(2), 199-207 (2007) · Zbl 1115.05033 · doi:10.1016/j.disc.2006.06.030
[14] Kemnitz A., Marangio M., Mihók P.: [r, s, t]-Chromatic numbers and hereditary properties of graphs. Discrete Math. 307(7-8), 916-922 (2007) · Zbl 1115.05034 · doi:10.1016/j.disc.2005.11.055
[15] Kemnitz A., Lehmann J.: [r, s, t]-Colorings of stars. Congressus Numerantium 185, 65-80 (2007) · Zbl 1137.05032
[16] Kouider M., Mahéo M.: Some bound for the b-chromatic number of a graph. Discrete Math. 256, 267-277 (2002) · Zbl 1008.05056 · doi:10.1016/S0012-365X(01)00469-1
[17] Ruskey, F., Sawada, J.: Bent Hamilton cycles in d-dimensional grid graphs. Electron. J. Comb. 10, #R1 (2003) · Zbl 1012.05105
[18] Schiermeyer I., Villà à M.S.: [r, s, t]-Colourings of paths. Opuscula Mathematica 27, 131-149 (2007) · Zbl 1146.05026
[19] Tigrine F., Kheddouci H.: The minimum feedback vertex set for Kronecker product of graphs. Utilitas Mathematica 74, 207-238 (2007) · Zbl 1192.05127
[20] Villà à, M.S.: [r, s, t]-Colourings of Paths, Cycles and Stars. Doctoral thesis, TU Bergakademie, Freiberg (2005) · Zbl 0991.05083
[21] Zhu X.: Star chromatic numbers and products of graphs. J. Graph Theory 16, 557-569 (1992) · Zbl 0766.05033 · doi:10.1002/jgt.3190160604
[22] Zhu X.: The fractional chromatic number of the direct product of graphs. Glasg. Math. J. 44, 103-115 (2002) · Zbl 0995.05052 · doi:10.1017/S0017089502010066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.