×

\(T\)-coloring of product graphs. (English) Zbl 1482.05109

Summary: Given a graph \(G=(V,E)\) and a finite set \(T\) of positive integers containing \(0,\) a \(T\)-coloring of \(G\) is a function \(f:V(G)\to Z^+\cup\{0\}\) for all \(u\neq w\) in \(V(G)\) such that if \(uw\in E(G)\) then \(|f(u)-f(w)|\notin T\). For a \(T\)-coloring \(f\) of \(G\), the \(f\)-span \(\mathrm{sp}_T^f(G)\) is the maximum value of \(|f(u)-f(w)|\) over all pairs \(u,w\) of vertices of \(G\). The \(T\)-span \(\mathrm{sp}_T(G)\) is the minimum \(f\)-span overall \(T\)-colorings of \(G\). The \(f\)-edge span of a \(T\)-coloring \(\mathrm{esp}_T^f(G)\) is the maximum value of \(|f(u)-f(w)|\) over all edges \(uw\) of \(G\). The \(T\)-edge span \(\mathrm{esp}_T(G)\) is the minimum \(f\)-edge span overall \(T\)-colorings of \(G\). This paper discusses the \(T\)-span and \(T\)-edge span of Cartesian, Join, Union and Tensor products of graphs. Also, we discuss the relation between Restricted span and Restricted edge span of graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
Full Text: DOI

References:

[1] Balakrishnan, R. and Ranganathan, K., A Text Book of Graph Theory (Springer, 2000). · Zbl 0938.05001
[2] Cozzens, M. B. and Roberts, F. S., T-Coloring of graphs and the channel assignment problem, Congr. Num.35 (1982) 191-208. · Zbl 0537.05023
[3] Chartrand, G. and Zhang, P., Chromatic graph theory, Discrete Mathematics and its Applications (CRC Press, Taylor and Francis Group, 2009). · Zbl 1169.05001
[4] Hale, W. K., Frequency assignment: Theory and applications, Proc. IEEE68 (1980) 1497-1514.
[5] Jai Roselin, S. and Benedict Michael Raj, L., T-Coloring of certain non-perfect Graphs, J. Appl. Sci. Comput.VI(II) (2019) 1456-1468.
[6] Justie, S.-T. J., Sun, I.-F. and Wu, P.-X., T-Coloring on folded hypercubes, Taiwanese J. Math.13(4) (2009) 1331-1341. · Zbl 1201.05038
[7] Murphey, R. A., Paradalos, P. M. and Resende, M. G. C., Frequency assignments problems, Handbook Combinat. Optimiz. (1999) 295-377. · Zbl 1253.90137
[8] Raychaudhuri, A., Further results on T-Coloring and Frequency assignment problems, SIAM J. Disc. Math.7 (1994) 605-613. · Zbl 0810.05026
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.