L(p,q)-labeling of graphs with interval representations
DISCUSSIONES MATHEMATICAE - GRAPH THEORY, cilt.43, sa.4, ss.1215-1235, 2023 (SCI-Expanded)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 43 Sayı: 4
- Basım Tarihi: 2023
- Doi Numarası: 10.7151/dmgt.2426
- Dergi Adı: DISCUSSIONES MATHEMATICAE - GRAPH THEORY
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED)
- Sayfa Sayıları: ss.1215-1235
- Süleyman Demirel Üniversitesi Adresli: Evet
Özet
We provide upper bounds on the L(p,q)-labeling number of graphs which have interval (or circular-arc) representations via simple greedy algorithms. We prove that there exists an L(p,q)-labeling with span at most max{2(p+q-1)Δ-4q+2, (2p-1)μ+(2q-1)Δ- 2q+1} for interval k-graphs, max{p,q}Δ for interval graphs, 3max{p,q}Δ+p for circular-arc graphs, 2(p+q-1)Δ-2q+1 for permutation graphs and (2p-1)Δ+(2q-1)(μ-1) for cointerval graphs. In particular, these improve existing bounds on L(p,q)-labeling of interval graphs and L(2,1)-labeling of permutation graphs. Furthermore, we provide upper bounds on the coloring of the squares of aforementioned classes.