1-perfectly orientable K[sub]4-minor-free and outerplanar graphsBrešar, Boštjan (Avtor) Hartinger, Tatiana Romina (Avtor) Kos, Tim (Avtor) Milanič, Martin (Avtor) 1-perfectly orientable graph▫$K_4$▫-minor-free graphouterplanar graphA graph ▫$G$▫ is said to be 1-perfectly orientable if it has an orientation ▫$D$▫ such that for every vertex ▫$v \in V(G)$▫, the out-neighborhood of ▫$v$▫ in ▫$D$▫ is a clique in ▫$G$▫. D. J. Skrien [J. Graph Theory 6, 309--316 (1982)] 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 ▫$K_4$▫-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.20182021-04-07 05:04:44Delo ni kategorizirano78962UDK: 519.17OceCobissID: 25342464COBISS_ID: 1540044740DOI: 10.1016/j.dam.2017.09.017ISSN pri članku: 0166-218Xsl