Characterization and recognition of some opposition and coalition graph classes

Van Bang Le, Thomas Podelleck

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, re…