On opposition graphs, coalition graphs, and bipartite permutation graphs

DOI10.1016/j.dam.2012.11.020zbMath1285.05063MaRDI QIDQ2442203

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

perfectly orderable graph; bipartite permutation graph; coalition graph; one-in-one-out graph; opposition graph

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Bipartite Analogues of Comparability and Cocomparability Graphs, Characterization and recognition of some opposition and coalition graph classes, Non-edge orientation and vertex ordering characterizations of some classes of bigraphs

Cites Work

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