Treelike comparability graphs |
| |
| Authors: | Sabine Cornelsen |
| |
| Institution: | a Universität Konstanz, Fachbereich Informatik & Informationswissenschaft, Germany
b Università dell’Aquila, Dipartimento di Ingegneria Elettrica e dell’Informazione, Italy |
| |
| Abstract: | An undirected graph is a treelike comparability graph if it admits a transitive orientation such that its transitive reduction is a tree. We show that treelike comparability graphs are distance hereditary. Utilizing this property, we give a linear time recognition algorithm. We then characterize permutation graphs that are treelike. Finally, we consider the Partitioning into Bounded Cliques problem on special subgraphs of treelike permutation graphs. |
| |
| Keywords: | Comparability graphs Edge orientation Transitive reduction Split decomposition Partition into bounded cliques |
| 本文献已被 ScienceDirect 等数据库收录！ |
