On characterizations for subclasses of directed co-graphs
From MaRDI portal
Abstract: Undirected co-graphs are those graphs which can be generated from the single vertex graph by disjoint union and join operations. Co-graphs are exactly the P_4-free graphs (where P_4 denotes the path on 4 vertices). Co-graphs itself and several subclasses haven been intensively studied. Among these are trivially perfect graphs, threshold graphs, weakly quasi threshold graphs, and simple co-graphs. Directed co-graphs are precisely those digraphs which can be defined from the single vertex graph by applying the disjoint union, order composition, and series composition. By omitting the series composition we obtain the subclass of oriented co-graphs which has been analyzed by Lawler in the 1970s and the restriction to linear expressions was recently studied by Boeckner. There are only a few versions of subclasses of directed co-graphs until now. By transmitting the restrictions of undirected subclasses to the directed classes, we define the corresponding subclasses for directed co-graphs. We consider directed and oriented versions of threshold graphs, simple co-graphs, co-simple co-graphs, trivially perfect graphs, co-trivially perfect graphs, weakly quasi threshold graphs and co-weakly quasi threshold graphs. For all these classes we provide characterizations by finite sets of minimal forbidden induced subdigraphs. Further we analyze relations between these graph classes.
Recommendations
- Characterizations for special directed co-graphs
- Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
- Directed path-width and directed tree-width of directed co-graphs
- scientific article; zbMATH DE number 3896983
- Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3896983 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 6271443 (Why is no real title available?)
- scientific article; zbMATH DE number 3064989 (Why is no real title available?)
- A complete axiomatisation for the inclusion of series-parallel partial orders
- A simple linear-time recognition algorithm for weakly quasi-threshold graphs
- An optimal path cover algorithm for cographs
- Arc-disjoint paths in decomposable digraphs
- Characterizations for special directed co-graphs
- Classes of directed graphs
- Comparing linear width parameters for directed graphs
- Complement reducible graphs
- Computing digraph width measures on directed co-graphs (extended abstract)
- Computing directed Steiner path covers for directed co-graphs (extended abstract)
- Dacey Graphs
- Digraphs
- Directed NLC-width
- Directed path-width and directed tree-width of directed co-graphs
- Directed path-width of sequence digraphs
- Directed tree-width
- Fully dynamic recognition algorithm and certificate for directed cographs
- Graphs of linear clique-width at most 3
- Laplacian spectrum of weakly quasi-threshold graphs
- Oriented coloring on recursively defined digraphs
- Oriented threshold graphs
- Partial homology relations -- satisfiability in terms of di-cographs
- The Pathwidth and Treewidth of Cographs
- The Recognition of Series Parallel Digraphs
- Threshold graphs and related topics
- Trivially perfect graphs
- Upper bounds to the clique width of graphs
- Words and graphs
Cited in
(4)- Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- scientific article; zbMATH DE number 5237243 (Why is no real title available?)
- Characterizations for special directed co-graphs
This page was built for publication: On characterizations for subclasses of directed co-graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2025109)
