On semi-transitive orientability of split graphs

Kitaev, Sergey and Pyatkin, Artem (2024) On semi-transitive orientability of split graphs. Information Processing Letters, 184. 106435. ISSN 1872-6119 (https://doi.org/10.1016/j.ipl.2023.106435)

[thumbnail of Kitaev-Pyatkin-IPL-2023-On-semi-transitive-orientability-of-split-graphs]
Preview
 Text. Filename: Kitaev_Pyatkin_IPL_2023_On_semi_transitive_orientability_of_split_graphs.pdf
Final Published Version
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (240kB)| Preview

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.

CORE (COnnecting REpositories)