The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
우리는 Ghouila-Houri의 정리와 유사한 진술이 상호 비교 가능성 그래프의 교대 방향에 대해 유지될 수 있는지 여부를 연구했습니다. 본 논문에서는 부정적인 대답을 제시한다. 우리는 상호 비교 가능성 그래프가 교대 및 비순환 방향을 갖는지 여부를 결정하는 것이 NP-완전임을 증명합니다. 따라서 비순환 교대 방향의 상호 비교 가능성 그래프는 교대 방향의 상호 비교 가능성 그래프의 적절한 하위 클래스를 형성합니다. 또한 분리 예, 즉 교대 방향이 비순환적이지 않도록 교대로 배향 가능한 상호 비교 가능성 그래프를 제공합니다.
Asahi TAKAOKA
Muroran Institute of Technology
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Asahi TAKAOKA, "A Note on the Intersection of Alternately Orientable Graphs and Cocomparability Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 9, pp. 1223-1227, September 2022, doi: 10.1587/transfun.2021DMP0001.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021DMP0001/_p
부
@ARTICLE{e105-a_9_1223,
author={Asahi TAKAOKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on the Intersection of Alternately Orientable Graphs and Cocomparability Graphs},
year={2022},
volume={E105-A},
number={9},
pages={1223-1227},
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.},
keywords={},
doi={10.1587/transfun.2021DMP0001},
ISSN={1745-1337},
month={September},}
부
TY - JOUR
TI - A Note on the Intersection of Alternately Orientable Graphs and Cocomparability Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1223
EP - 1227
AU - Asahi TAKAOKA
PY - 2022
DO - 10.1587/transfun.2021DMP0001
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2022
AB - 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.
ER -