20.500.12556/DKUM-78962 1-perfectly orientable K[sub]4-minor-free and outerplanar graphs A 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. 1-perfectly orientable graph ▫$K_4$▫-minor-free graph outerplanar graph 1-popolno usmerljiv graf graf brez ▫$K_4$▫ minorja zunanje ravninski graf true true false Angleški jezik Angleški jezik Delo ni kategorizirano 2021-04-07 05:04:44 2022-09-20 09:12:13 2022-09-20 09:12:15 0000-00-00 00:00:00 2018 0 0 33-45 Vol. 248 Oct. 2018 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 25342464 1540044740 10.1016/j.dam.2017.09.017 0166-218X https://doi.org/10.1016/j.dam.2017.09.017 1 0310f2d4-974e-11eb-8047-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=149658 Fakulteta za naravoslovje in matematiko 0 0 0