Characterization and recognition of some opposition and coalition graph classes

DOI10.1016/J.DAM.2015.06.007zbMATH Open1350.05047arXiv1507.00557OpenAlexW2963569157MaRDI QIDQ344867FDOQ344867

Thomas Podelleck, Van Bang Le

Publication date: 24 November 2016

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

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• 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)