IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Online ISSN : 1745-1337
Print ISSN : 0916-8508
Special Section on Discrete Mathematics and Its Applications
A Note on the Intersection of Alternately Orientable Graphs and Cocomparability Graphs
Asahi TAKAOKA
Author information
JOURNAL RESTRICTED ACCESS

2022 Volume E105.A Issue 9 Pages 1223-1227

Details
Abstract

We studied whether a statement similar to the Ghouila-Houri's theorem might hold for alternating orientations of cocomparability graphs. In this paper, we give the negative answer. We prove that it is NP-complete to decide whether a cocomparability graph has an orientation that is alternating and acyclic. Hence, cocomparability graphs with an acyclic alternating orientation form a proper subclass of alternately orientable cocomparability graphs. We also provide a separating example, that is, an alternately orientable cocomparability graph such that no alternating orientation is acyclic.

Content from these authors
© 2022 The Institute of Electronics, Information and Communication Engineers
Previous article Next article
feedback
Top