On opposition graphs, coalition graphs, and bipartite permutation graphs

DOI10.1016/J.DAM.2012.11.020zbMATH Open1285.05063OpenAlexW1986605895MaRDI QIDQ2442203FDOQ2442203

Authors: Van Bang Le 

Publication date: 2 April 2014

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

Full work available at URL: https://doi.org/10.1016/j.dam.2012.11.020

Recommendations

• Characterization and recognition of some opposition and coalition graph classes
• Bipartite permutation graphs
• Opposition graphs are strict quasi-parity graphs
• scientific article; zbMATH DE number 1156661
• Polar permutation graphs are polynomial-time recognisable

zbMATH Keywords

bipartite permutation graphcoalition graphone-in-one-out graphopposition graphperfectly orderable graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Graph Classes: A Survey
• Efficient graph representations
• The strong perfect graph theorem
• Transitiv orientierbare Graphen
• Bipartite permutation graphs
• Characterizations of totally balanced matrices
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• All variations on perfectly orderable graphs
• Recognition of some perfectly orderable graph classes
• Permuting matrices to avoid forbidden submatrices
• On the complexity of recognizing a class of perfectly orderable graphs
• Perfectly orderable graphs: A survey
• Some classes of perfectly orderable graphs
• Which claw-free graphs are perfectly orderable?
• Bipolarizable graphs
• On the complexity of recognizing perfectly orderable graphs
• A translation of Gallai's paper: `Transitiv orientierbare Graphen'
• Efficient parallel algorithms for bipartite permutation graphs

Cited In (4)

• Opposition graphs are strict quasi-parity graphs
• Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
• Bipartite Analogues of Comparability and Cocomparability Graphs
• Characterization and recognition of some opposition and coalition graph classes

This page was built for publication: On opposition graphs, coalition graphs, and bipartite permutation graphs

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