2025/04/27 by Tithi Dwary, Dwary, Tithi, Khyodeno Mozhui +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2504.19167
openalex publication_date 2025/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.