On semi-transitive orientability of split graphs

DOI10.1016/J.IPL.2023.106435MaRDI QIDQ6121421zbMATH OpenOpenAlexFDO

Authors Sergey Kitaev, Artem Pyatkin

Publication date 26 March 2024

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2110.08834

zbMATH Keywords

circular ones propertycomputational complexitypolynomial solvabilitysemi-transitive orientationsplit graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: A directed graph is semi-transitive if and only if it is acyclic and for any directed path $u_{1}ightarrow{u}_{2}ightarrowcdotsightarrow{u}_t$, $tgeq2$, either there is no edge from $u_1$ to $u_t$ or all edges $u_{i}ightarrow{u}_j$ exist for $1leqi<jleqt$. 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 spit graphs was recently studied 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. We also characterize, in terms of minimal forbidden induced subgraphs, semi-transitively orientable split graphs with the size of the independent set at most 3, hence extending the known classification of such graphs with the size of the clique at most 5.

Cites work

• scientific article; zbMATH DE number 3614694 (Why is no real title available?)
• Incidence matrices and interval graphs
• Isomorphism of graph classes related to the circular-ones property
• Matrix characterizations of circular-arc graphs
• On representable graphs
• PC trees and circular-ones arrangements.
• Representing split graphs by words
• Semi-transitive orientations and word-representable graphs
• Semi-transitivity of directed split graphs generated by morphisms
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Vertex deletion on split graphs: beyond 4-hitting set
• Word-representability of split graphs
• Word-representability of split graphs generated by morphisms
• Word-Representable Graphs: a Survey
• Words and graphs

Cited in

(6)

• New tools to study 1-11-representation of graphs
• Word-representable graphs from a word's perspective
• On the word-representability of K_m-K_n graphs
• Boxicity of a class of split graphs using words
• Characterization of word-representable split graphs with an independent set of fixed size
• Word-representable co-bipartite graphs: representation number, speed, and entropy

This page was built for publication: On semi-transitive orientability of split graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6121421)