On opposition graphs, coalition graphs, and bipartite permutation graphs

DOI10.1016/J.DAM.2012.11.020MaRDI QIDQ2442203zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)