On L(h,k)-labelings of oriented graphs
ResumoWe compare the behaviour of the $L(h,k)$-number of undirected and oriented graphs in terms of maximum degree, highlighting differences between the two contexts. In particular, we prove that, for every $h$ and $k$, oriented graphs with bounded degree in every block of their underlying graph (for instance, oriented trees and oriented cacti) have bounded $L(h,k)$-number, giving an upper bound on this number which is sharp up to a multiplicative factor $4$.
Chang, G. J. and Liaw, S.-C. (2003). The L(2, 1)-labeling problem on ditrees. Ars Combinatoria, 66:23–31.
Chen, Y.-T., Chia, M.-L., and Kuo, D. (2009). L(p, q)-labeling of digraphs. Discrete applied mathematics, 157(8):1750–1759.
Colucci, L. and Gyori, E. (2021+). On L(2, 1)-labelings of oriented graphs. Discussiones Mathematicae Graph Theory. In press.
Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):1497–1514.
Yeh, K.-C. (1990). Labeling graphs with a condition at distance two. PhD thesis, University of South Carolina.