Partial characterizations of 1-perfectly orientable graphs
From MaRDI portal
Abstract: We study the class of 1-perfectly orientable graphs, that is, graphs having an orientation in which every out-neighborhood induces a tournament. 1-perfectly orientable graphs form a common generalization of chordal graphs and circular arc graphs. Even though they can be recognized in polynomial time, little is known about their structure. In this paper, we develop several results on 1-perfectly orientable graphs. In particular, we: (i) give a characterization of 1-perfectly orientable graphs in terms of edge clique covers, (ii) identify several graph transformations preserving the class of 1-perfectly orientable graphs, (iii) exhibit an infinite family of minimal forbidden induced minors for the class of 1-perfectly orientable graphs, and (iv) characterize the class of 1-perfectly orientable graphs within the classes of cographs and of cobipartite graphs. The class of 1-perfectly orientable co-bipartite graphs coincides with the class of co-bipartite circular arc graphs.
Recommendations
Cites work
- A characterization of competition graphs
- A characterization of normal fraternally orientable perfect graphs
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
- Algorithmic graph theory and perfect graphs
- An algorithm for fraternal orientation of graphs
- Approximation algorithms for intersection graphs
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Characterizing circular-arc graphs
- Computing roots of graphs is hard
- Cyclical orientations of graphs
- Digraphs
- Fraternal augmentations, arrangeability and linear Ramsey numbers
- Graphs of separability at most 2
- scientific article; zbMATH DE number 165077 (Why is no real title available?)
- In-tournament digraphs
- Intersection graphs of concatenable subtrees of graphs
- Intersection graphs of proper subtrees of unicyclic graphs
- List homomorphisms and circular arc graphs
- Normal fraternally orientable graphs satisfy the strong perfect graph conjecture
- On cyclically orientable graphs
- On the Computation of the Competition Number of a Graph
- String graphs. I: The number of critical nonstring graphs is infinite
- Structural conditions for cycle completable graphs
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- Supereulerian graphs and excluded induced minors
- The square root of a graph
- Two remarks on circular arc graphs
Cited in
(11)- A characterization of normal fraternally orientable perfect graphs
- Avoidable vertices and edges in graphs: existence, characterization, and applications
- 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- 1-perfectly orientable \(K_{4}\)-minor-free and outerplanar graphs
- \(1\)-perfectly orientable graphs and graph products
- scientific article; zbMATH DE number 6794321 (Why is no real title available?)
- Bisimplicial separators
- Induced minor models. I: Structural properties and algorithmic consequences
- Orientations without forbidden patterns on three vertices
- Detecting \(K_{2,3}\) as an induced minor
This page was built for publication: Partial characterizations of 1-perfectly orientable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5272923)
