On the structure of 1-perfectly orientable graphs.
Tatiana Romina Hartinger, Martin Milanič · arXiv (Cornell University) · 2014
We study the class of 1-perfectly orientable (1-p.o.) graphs, that is, graphs having an ori-entation in which every out-neighborhood induces a tournament. 1-p.o. graphs form a common generalization of chordal graphs and circular arc graphs. Even though 1-p.o. graphs can be recognized in polynomial time, little is known about their structure. In this paper, we prove several structural results about 1-p.o. graphs and characterizations of 1-p.o. graphs in special graph classes. This includes: (i) a characterization of 1-p.o. graphs in terms of edge clique covers, (ii) identification of several graph transformations preserving the class of 1-p.o. graphs, (iii) a complete characterization of 1-p.o. cographs and of 1-p.o. complements of forests, and (iv) an infinite family of minimal forbidden induced minors for the class of 1-p.o. graphs.