2015/06/16 by Pavel Klavík, Klavík, Pavel, Peter Zeman +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topics in Algebra #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1506.05064
openalex publication_date 2015/06/16 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Comparability graphs are graphs which have transitive orientations. The dimension of a poset is the least number of linear orders whose intersection gives this poset. The dimension \rm dim(X) of a comparability graph X is the dimension of any transitive orientation of X, and by k-DIM we denote the class of comparability graphs X with \rm dim(X) ≤ k. It is known that the complements of comparability graphs are exactly function graphs and permutation graphs equal 2-DIM. In this paper, we characterize the automorphism groups of permutation graphs similarly to Jordan's characterization for trees (1869). For permutation graphs, there is an extra operation, so there are some extra groups not realized by trees. For k ≥ 4, we show that every finite group can be realized as the automorphism group of some graph in k-DIM, and testing graph isomorphism for k-DIM is GI-complete.