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 ε 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 generalizat...

Full description

Saved in:
Bibliographic Details
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)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771