On semi-transitive orientability of split graphs

Sergey Kitaev, Artem Pyatkin

Research output: Contribution to journalArticlepeer-review

14 Downloads (Pure)

Abstract

A directed graph is semi-transitive if and only if it is acyclic and for any directed path u 1 → u 2 → ⋯ → u t , t ≥ 2 , either there is no edge from u 1 to u t or all edges u i → u j exist for 1 ≤ i < j ≤ t . An undirected graph is semi-transitive if it admits a semi-transitive orientation. Recognizing semi-transitive orientability of a graph is an NP-complete problem. A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Semi-transitive orientability of split graphs was recently studied in a series of papers in the literature. The main result in this paper is proving that recognition of semi-transitive orientability of split graphs can be done in a polynomial time.
Original languageEnglish
Article number106435
Number of pages4
JournalInformation Processing Letters
Volume184
Early online date1 Sept 2023
DOIs
Publication statusPublished - Feb 2024

Keywords

  • semi-transitive orientation
  • split graph
  • polynomial solvability
  • circular ones property

Fingerprint

Dive into the research topics of 'On semi-transitive orientability of split graphs'. Together they form a unique fingerprint.

Cite this