A Note on Threshold Dimension of Permutation Graphs

A graph $G(V,E)$ is a threshold graph if there exist non-negative reals $w_v, v \in V$and$t$suchthatforevery$U \subseteq V$,$\sum_{v \in U} w_v\leq t$ifandonlyif$U$isastableset\mathrm{.}Thethresholddimensionofagraph$G(V,E)$,denotedas$t(G)$,isthesmallestinteger$k$suchthat$E$ can be covered by $k$ threshold spanning subgraphs of $G$. A permutation graph is a graph that can be represented as the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane. In this paper we will show that if $G$ is a permutation graph then $t(G)\le \alpha (G)$ (where $\alpha (G)$ is the cardinality of maximum independent set in $G$) and this bound is tight. As a corollary we will show that $t(G)\le \frac{n}{2}$ where $n$ is the number of vertices in the permutation graph $G$. This bound is also tight.