1-perfectly orientable K^sub 4^-minor-free and outerplanar graphs

• Published in: Discrete Applied Mathematics 2018-10, Vol.248, p.33
• Main Authors: Brešar, Boštjan, Hartinger, Tatiana Romina, Kos, Tim, Milanic, Martin
• Format: Article
• Language: English
• Subjects: Combinatorics; Graph algorithms; Graphs; Polynomials; Reduction; Structural analysis; Theorems; Trees (mathematics)
• ISSN: 0166-218X; 1872-6771

A graph G is said to be 1-perfectly orientable if it has an orientation D such that for every vertex v ε V (G), the out-neighborhood of v in D is a clique in G. In 1982, Skrien posed the problem of characterizing the class of 1-perfectly orientable graphs. This graph class forms a common generalization of the classes of chordal and circular arc graphs; however, while polynomially recognizable via a reduction to 2-SAT, no structural characterization of this intriguing class of graphs is known. Based on a reduction of the study of 1-perfectly orientable graphs to the biconnected case, we characterize, both in terms of forbidden induced minors and in terms of composition theorems, the classes of 1-perfectly orientable K4-minor-free graphs and of 1-perfectly orientable outerplanar graphs. As part of our approach, we introduce a class of graphs defined similarly as the class of 2-trees and relate the classes of graphs under consideration to two other graph classes closed under induced minors studied in the literature: cyclically orientable graphs and graphs of separability at most 2.