Characterization of Split Comparability Graphs

Tithi Dwary, Khyodeno Mozhui, K. V. Krishna · 2025

Read Characterization of Split Comparability Graphs by Tithi Dwary, Khyodeno Mozhui, K. V. Krishna (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19167.txt.

Introduction

Tithi Dwary, Khyodeno Mozhui, and Krishna sort which split graphs can also be read as order graphs, in a paper from two thousand twenty-five. A split graph divides its points into a fully linked clique and an unlinked set. The order side asks whether arrows can point along a ranking without cycles.

A labeling test marks exactly which split graphs qualify. From that test, any such graph needs at most three ranking words to encode it. The bound also re-proves a known cap on the dimension of split orders. Readers in graph theory get a tidy test plus a sharp encoding cap in one pass.

Catalog record

CREATORTithi Dwary, Khyodeno Mozhui, K. V. Krishna
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-19167

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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 i<j\leq k . It was proved that a graph is word-representable if and only if it admits a semi-transitive orientation [ 7 ] . For a detailed introduction to the theory of word-representable graphs, one can refer to the monograph [ 9 ] . A word-representable graph G is said to be permutationally representable if there is a word w of the form p_{1}p_{2}\cdots p_{k} representing G , where each p_{i} is a permutation on the vertices of G ; in this case G is called a permutationally k -representable graph. Moreover, we say w permutationally represents G . The permutation-representation number (in short, prn ) of G , denoted by \mathcal{R}^{p}(G) , is the smallest number k such that G is permutationally k -representable. It was shown in [ 12 ] that a graph is permutationally representable if and only if it is a comparability graph - a graph which admits a transitive orientation. Recall that an orientation of a graph G=(V,E) is transitive if \overrightarrow{ab}\in E , \overrightarrow{bc}\in E , then \overrightarrow{ac}\in E , for all a,b,c\in V . Note that a transitive orientation is also a semi-transitive orientation, but not conversely. It was reconciled in [ 13 ] that if G is a comparability graph, then \mathcal{R}^{p}(G) is precisely the dimension of any induced partially ordered set (poset) of G . The class of graphs with representation number at most two is characterized as the class of circle graphs [ 6 ] and the class of graphs with prn at most two is the class of permutation graphs [ 3 ] . In general, the problems of determining the representation number of a word-representable graph, and the prn of a comparability graph are computationally hard [ 6 , 14 ] . A graph G=(V,E) is a split graph if the vertex set V can be partitioned as I\cup C , where I induces an independent set, and C induces a clique in G . In this paper, we consider the clique C for a split graph G=(I\cup C,E) to be inclusion wise maximal, i.e., no vertices of I is adjacent to all vertices of C . The class of word-representable split graphs was characterized in [ 8 ] using semi-transitive orientation. Further, a forbidden induced subgraph characterization for the class of split comparability graphs (split graphs which are transitively orientable) can be found in [ 4 ] . Recall from [ 5 ] that a partial order is called a split order if the corresponding comparability graph is a split graph. It was proved in [ 5 ] that the dimension of a split order is at most three, and the bound is tight. In the following, we recall some relevant results known for the class of split graphs restricted to permutation graphs, comparability graphs and word-representable graphs. Theorem 1.1 ( [ 1 ] ) Let G be a split graph. Then, G is a permutation graph if and only if G is a \mathcal{B} -free graph, where \mathcal{B} is the class of graphs given in Fig. 1 . B_{1} B_{2} B_{3} B_{4} Figure 1: The family of graphs \mathcal{B} Theorem 1.2 ( [ 4 ] ) Let G be a split graph. Then, G is a comparability graph if and only if G contains no induced subgraph isomorphic to B_{1} , B_{2} , or B_{3} (depicted in Fig. 1 ). Theorem 1.3 ( [ 8 ] ) Let G=(I\cup C,E) be a split graph with |C|=k , and S be a semi-transitive orientation of G with the longest directed path P:c_{1}\rightarrow\cdots\rightarrow c_{k} in C . Then, the vertices of I can be subdivided into the following three, possibly empty, disjoint types. For a\in I , (a) N(a)=\{c_{1},\ldots,c_{m}\}\cup\{c_{n},\ldots,c_{k}\} , for some 1\leq m<n\leq k , such that \overrightarrow{c_{i}a}\in S for all 1\leq i\leq m and \overrightarrow{ac_{i}}\in S for all n\leq i\leq k ; (b) N(a)=\{c_{l},\ldots,c_{r}\} , for some 1\leq l\leq r\leq k , such that \overrightarrow{c_{i}a}\in S for all l\leq i\leq r ( a is a sink ) ; or (c) N(a)=\{c_{l},\ldots,c_{r}\} , for some 1\leq l\leq r\leq k , such that \overrightarrow{ac_{i}}\in S for all l\leq i\leq r ( a is a source ) . For any two integers a\leq b , [a,b] in Theorem 1.4 denotes the set of integers \{a,a+1,\ldots,b\} . Theorem 1.4 ( [ 8 , 11 ] ) Let G=(I\cup C,E) be a split graph. Then, G is semi-transitively orientable if and only if the vertices of C can be labeled from 1 to k=|C| in such a way that for each a,b\in I the following holds. (i) Either N(a)=[1,m]\cup[n,k] , for m<n , or N(a)=[l,r] , for l\leq r . (ii) If N(a)=[1,m]\cup[n,k] and N(b)=[l,r] , for m<n and l\leq r , then l>m or r<n . (iii) If N(a)=[1,m]\cup[n,k] and N(b)=[1,m^{\prime}]\cup[n^{\prime},k] , for m<n and m^{\prime}<n^{\prime} , then m^{\prime}<n and m<n^{\prime}

Read the complete text