L(p,q)-Labeling of Graphs with Interval Representations

DOI10.7151/DMGT.2426MaRDI QIDQ6325138zbMATH OpenFDO

Authors Mehmet Akif Yetim

Publication date 11 September 2019

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Combinatorics of partially ordered sets (06A07)

Abstract: 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 $max2(p+q-1)Delta-4q+2,(2p-1)mu+(2q-1)Delta-2q+1$ for interval $k$-graphs, $maxp,qDelta$ for interval graphs, $3maxp,qDelta+p$ for circular-arc graphs, $2(p+q-1)Delta-2q+1$ for permutation graphs and $(2p-1)Delta+(2q-1)(mu-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.

This page was built for publication: $L(p,q)$-Labeling of Graphs with Interval Representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325138)