1-perfectly orientable K₄-minor-free and outerplanar graphs

DOI10.1016/J.ENDM.2016.09.035MaRDI QIDQ510581zbMATH OpenOpenAlexFDO

Authors Boštjan Brešar, Tim Kos, Tatiana Romina Hartinger, Martin Milanič

Publication date 13 February 2017

Full work available at URL https://arxiv.org/abs/1604.04598

zbMATH Keywords

1-perfectly orientable graph\(K_{4}\)-minor-free graphouterplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: A graph $G$ is said to be $1$-perfectly orientable if it has an orientation such that for every vertex $vinV(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 $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$.

Recommendations

• 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
• Partial characterizations of 1-perfectly orientable graphs
• \(1\)-perfectly orientable graphs and graph products
• Graphes parfaitement ordonnables généralisés. (Generalized perfectly orderable graphs)
• New properties of perfectly orderable graphs and strongly perfect graphs

Cites work

• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• An algorithm for fraternal orientation of graphs
• Approximation algorithms for intersection graphs
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• In-tournament digraphs
• Partial characterizations of 1-perfectly orientable graphs

Cited in

(2)

• 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
• Partial characterizations of 1-perfectly orientable graphs

This page was built for publication: 1-perfectly orientable \(K_{4}\)-minor-free and outerplanar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510581)