Characterization of Split Comparability Graphs Tithi Dwary, Khyodeno Mozhui, K. V. Krishna Abstract A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. A split comparability graph is a split graph which is transitively orientable. In this work, we characterize split comparability graphs in terms of vertex labelling. Further, using this characterization, we prove that the permutation-representation number of a split comparability graph is at most three. This gives us an alternative proof of the result in order theory that the dimension of a split order is at most three. 1 Introduction and Preliminaries A word is a finite sequence of letters taking from a finite set. A subword u of a word w is a subsequence of w , denoted by u\ll w . For instance, aabccb\ll acabbccb . Let w be a word over a set X , and A\subseteq X . Then, the subword of w restricted to the elements of A is denoted by w|_{A} . For example, if w=acabbccb , then w|_{\{a,b\}}=aabbb . For a word w , if w|_{\{a,b\}} is of the form abab\cdots or baba\cdots , which can be of even or odd length, we say the letters a and b alternate in w ; otherwise we say a and b do not alternate in w . A k -uniform word is a word in which every letter occurs exactly k times. For a word w , we write w^{R} to denote its reversal. A simple graph G=(V,E) is called a word-representable graph, if there exists a word w over V such that for all a,b\in V , \overline{ab}\in E if and only if a and b alternate in w . A word-representable graph G is said to be k -word-representable if there is a k -uniform word representing it. In [ 10 ] , It was proved that every word-representable graph is k -word-representable, for some k . The representation number of a word-representable graph G , denoted by \mathcal{R}(G) , is defined as the smallest number k such that G is k -word-representable. An orientation of a graph is semi-transitive if it is acyclic, and for any directed path a_{1}\rightarrow a_{2}\rightarrow\cdots\rightarrow a_{k} either there is no edge between a_{1} and a_{k} , or a_{i}\rightarrow a_{j} is an edge for all 1\leq im or r1 , with \overrightarrow{ac_{i}}\in D for all l\leq i\leq k (a is a source ) . Proof Since every transitive orientation is also a semi-transitive orientation, if a\in I , then a belongs to one of the three types defined in Theorem 1.3 . Note that the elements of type (a) are precisely in I_{1} . Suppose a is of type (b) so that N(a)=\{c_{l},\ldots,c_{r}\} , for some 1\leq l\leq r\leq k , such that \overrightarrow{c_{i}a}\in D for all l\leq i\leq r . If l>1 , then we have \overrightarrow{c_{1}c_{l}}\in D and \overrightarrow{c_{l}a}\in D , but \overrightarrow{c_{1}a}\notin D ; a contradiction to D is a transitive orientation of G . Thus, we must have l=1 . Further, as C is a maximal clique in G , we have r1 , then r1 . (ii) If N(a)=[1,r] and N(b)=[l,k] , for r1 , then r1 and m1\} . Further, we define an orientation D of G as per the following: • \overrightarrow{ij}\in D , for all 1\leq is (as \overrightarrow{sc}=\overrightarrow{bc}\in D ). But as a\in A_{3} and \overrightarrow{as}\in D , by the property of A_{3} , we have \overrightarrow{at}=\overrightarrow{ac}\in D , but \overrightarrow{ac}\not\in D . If c\in A_{2} , then N(c)=[1,r] , for some rs . Moreover, as \overrightarrow{as}\in D , we have n\leq s1\} Then, from Theorem 3.1 , we have A_{1},A_{2} and A_{3} are mutually disjoint, and I=A_{1}\cup A_{2}\cup A_{3} . For a\in A_{1} , let N(a)=[1,m_{a}]\cup[n_{a},k] , for a\in A_{2} , let N(a)=[1,r_{a}] , and for a\in A_{3} , let N(a)=[l_{a},k] . By Theorem 3.1 (iv) , since m_{a}d then 7 Assign d=m . 8 end if 9 Replace m in q_{1} with ma . 10 Replace n in q_{2} with an . 11 end if 12 else if a\in A_{2} then 13 Let N(a)=[1,r] . 14 Replace r in q_{2} with ra . 15 Update q_{3} with q_{3}a . 16 end if 17 else 18 Let N(a)=[l,k] . 19 Replace l in q_{2} with al . 20 Replace l in q_{3} with al . 21 end if 22 end for 23 Update q_{1} with (q_{2}|_{A_{3}})^{R}q_{1}(q_{2}|_{A_{2}})^{R} . 24 Replace d in q_{3} with d(q_{1}|_{A_{1}})^{R} . 25 return the word q_{1}q_{2}q_{3} Remark 2 In Algorithm 1 , note that the order of the vertices of C , i.e., 12\cdots k , in the permutations q_{1},q_{2} , and q_{3} do not alter when they are updated. Hence, we have z|_{C}=12\cdots k12\cdots k12\cdots k . Remark 3 Note that, the set A\subseteq I defined in Section 3 of [ 2 ] and the set A_{1} are identical for a split comparability graph G . Moreover, the lines related to insertion of the elements of A in p_{1} , p_{2} and p_{3} in Algorithm 1 of [ 2 ] are exactly the same as the lines on insertion of the elements of A_{1} in q_{1} , q_{2} and q_{3} in Algorithm 1 . Hence, the positions of the vertices of A_{1} in q_{1},q_{2} , and q_{3} with respect to the vertices of C are same as the positions of the vertices of A in p_{1},p_{2},p_{3} with respect to the vertices of C , respectively, i.e., p_{1}|_{A\cup C}=q_{1}|_{A_{1}\cup C} , p_{2}|_{A\cup C}=q_{2}|_{A_{1}\cup C} and p_{3}|_{A\cup C}=q_{3}|_{A_{1}\cup C} . Lemma 3 For a,b\in V , if a and b are adjacent in G , then a and b alternate in the word z . Proof As I is an independent set in G , note that at least one of a and b is in C . Suppose both a,b\in C . As the vertices of C are labeled from 1 to k , we have a=i and b=j , for some 1\leq i,j\leq k . Thus, in view of Remark 2 , we have z|_{\{a,b\}}=ababab , if i1 . Thus, we have l_{a}b\ll q_{1} , l_{a}b\ll q_{2} , and l_{a}b\ll q_{3} . As a\in A_{3} , replacing l_{a} in q_{2} with al_{a} (see line 19) and replacing l_{a} in q_{3} with al_{a} (see line 20), we have al_{a}b\ll q_{2} and al_{a}b\ll q_{3} , respectively. Further, by line 23, we have al_{a}b\ll q_{1} . Hence, ab\ll q_{1} , ab\ll q_{2} , and ab\ll q_{3} so that a and b alternate in the word z . ∎ Lemma 4 If a,b\in I , then a and b do not alternate in z . Proof Since I=A_{1}\cup A_{2}\cup A_{3} , we consider the following cases. • Case 1: a,b\in A_{1} . In view of Remark 3 and Case 1 in the proof of Lemma 3 in [ 2 ] , we conclude that a and b do not alternate in the word z . • Case 2: a,b\in A_{2} . Without loss of generality, suppose ab\ll q_{2} . Then, by line 23 of Algorithm 1 , we have ba\ll q_{1} . Thus, a and b do not alternate in the word z . • Case 3: a,b\in A_{3} . Without loss of generality, suppose ab\ll q_{2} . Then, ba\ll q_{1} (by line 23). Thus, a and b do not alternate in the word z . • Case 4: a\in A_{1} and b\in A_{2} . By line 23 of Algorithm 1 , we have ab\ll q_{1} . Note that N(a)=[1,m_{a}]\cup[n_{a},k] , for m_{a}1 . Then, in view of Remark 1 , we have m_{a}\leq d1 . Then, from Theorem 3.1 (ii) , we have r_{a}1 . Since b\notin N(a) , we have 1\leq b