Characterization and recognition of some opposition and coalition graph classes

详细信息    查看全文

• 作者：Van Bang Le ; ^{le@informatik.uni-rostock.de} ; Thomas Podelleck ^{thomas.podelleck@gmail.com}
• 关键词：Perfectly orderable graph ; One-in-one-out graph ; Opposition graph ; Coalition graph ; Perfect graph
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：261-272
• 全文大小：541 K
• 卷排序：216

文摘

A graph is an opposition graph, respectively, a coalition graph, if it admits an acyclic orientation which puts the two end-edges of every chordless 4-vertex path in opposition, respectively, in the same direction. Opposition and coalition graphs have been introduced and investigated in connection to perfect graphs. Recognizing and characterizing opposition and coalition graphs are long-standing open problems. This paper gives characterizations for opposition graphs and coalition graphs on some restricted graph classes. Implicit in our arguments are polynomial time recognition algorithms for these graphs. We also give a good characterization for the so-called generalized opposition graphs.