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 language | English |
|---|---|
| Article number | 106435 |
| Number of pages | 4 |
| Journal | Information Processing Letters |
| Volume | 184 |
| Early online date | 1 Sept 2023 |
| DOIs | |
| Publication status | Published - Feb 2024 |
Funding
The work of the second author was partially supported by the state contract of the Sobolev Institute of Mathematics (project FWNF-2022-0019 ). The authors are grateful to the unknown referee for helpful comments.
Keywords
- semi-transitive orientation
- split graph
- polynomial solvability
- circular ones property