On semi-transitive orientability of split graphs

DOI10.1016/j.ipl.2023.106435arXiv2110.08834OpenAlexW4386374895MaRDI QIDQ6121421

Artem V. Pyatkin, Sergey Kitaev

Publication date: 26 March 2024

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

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

zbMATH Keywords

computational complexitysplit graphpolynomial solvabilitysemi-transitive orientationcircular ones property

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Words and graphs
• Semi-transitive orientations and word-representable graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• PC trees and circular-ones arrangements.
• Word-representability of split graphs
• Word-representability of split graphs generated by morphisms
• Representing split graphs by words
• Semi-transitivity of directed split graphs generated by morphisms
• Incidence matrices and interval graphs
• Matrix characterizations of circular-arc graphs
• Word-Representable Graphs: a Survey
• On representable graphs
• Vertex deletion on split graphs: beyond 4-hitting set

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