Characterization and recognition of some opposition and coalition graph classes

DOI10.1016/J.DAM.2015.06.007MaRDI QIDQ344867zbMATH OpenOpenAlexFDO

Authors Van Bang Le, Thomas Podelleck

Publication date 24 November 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

perfect graphcoalition graphone-in-one-out graphopposition graphperfectly orderable graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Perfect graphs (05C17)

Abstract: 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.

Recommendations

• On opposition graphs, coalition graphs, and bipartite permutation graphs
• Opposition graphs are strict quasi-parity graphs
• On the coalition number of trees
• Self-coalition graphs
• A simple nc recognition algorithm for welsh-powell opposition graphs

Cites work

• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• A simple nc recognition algorithm for welsh-powell opposition graphs
• All variations on perfectly orderable graphs
• Bipolarizable graphs
• Distance-hereditary comparability graphs
• Distance-hereditary graphs
• Efficient graph representations
• Graph Classes: A Survey
• On opposition graphs, coalition graphs, and bipartite permutation graphs
• On sources in comparability graphs, with applications
• On the complexity of recognizing a class of perfectly orderable graphs
• On the complexity of recognizing perfectly orderable graphs
• On the recognition of bipolarizable and \(P_4\)-simplicial graphs
• Perfectly orderable graphs: A survey
• Recognition of some perfectly orderable graph classes
• Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs
• Some classes of perfectly orderable graphs
• The strong perfect graph theorem
• Welsh-Powell opposition graphs
• Which claw-free graphs are perfectly orderable?

Cited in

(4)

• On opposition graphs, coalition graphs, and bipartite permutation graphs
• Opposition graphs are strict quasi-parity graphs
• Self-coalition graphs
• On the coalition number of trees

This page was built for publication: Characterization and recognition of some opposition and coalition graph classes

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