On semi-transitive orientability of split graphs Full article
| Journal |
Information Processing Letters
ISSN: 0020-0190 |
||||||
|---|---|---|---|---|---|---|---|
| Output data | Year: 2024, Volume: 184, Article number : 106435, Pages count : 4 DOI: 10.1016/j.ipl.2023.106435 | ||||||
| Tags | Semi-transitive orientation, Split graph, Polynomial solvability, Circular ones property, Computational complexity | ||||||
| Authors |
|
||||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
Abstract:
Adirected graph is semi-transitive if and only if it is acyclic and for any directed path u1 →u2 →···→ut, t ≥2, either there is no edge from u1 to ut or all edges ui → uj 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. Asplit 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.
Cite:
Kitaev S.
, Pyatkin A.
On semi-transitive orientability of split graphs
Information Processing Letters. 2024. V.184. 106435 :1-4. DOI: 10.1016/j.ipl.2023.106435 WOS Scopus РИНЦ OpenAlex
On semi-transitive orientability of split graphs
Information Processing Letters. 2024. V.184. 106435 :1-4. DOI: 10.1016/j.ipl.2023.106435 WOS Scopus РИНЦ OpenAlex
Dates:
| Submitted: | Sep 10, 2022 |
| Accepted: | Aug 28, 2023 |
| Published online: | Sep 1, 2023 |
| Published print: | Apr 2, 2024 |
Identifiers:
| Web of science: | WOS:001076813300001 |
| Scopus: | 2-s2.0-85170572963 |
| Elibrary: | 64853990 |
| OpenAlex: | W4386374895 |