Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs
From MaRDI portal
Publication:2178334
DOI10.1007/s10479-017-2712-zzbMath1441.05087arXiv1601.00032OpenAlexW2769048201MaRDI QIDQ2178334
Xavier Warnes, Guillermo Durán, Martín D. Safe
Publication date: 11 May 2020
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1601.00032
forbidden induced subgraphsrecognition algorithmstree-cographsco-bipartite graphs\(P_4\)-tidy graphsneighborhood-perfect graphs
Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A survey of the algorithmic aspects of modular decomposition
- On the hardness of approximating minimum vertex cover
- The strong perfect graph theorem
- A multivariate interlace polynomial and its computation for graphs of bounded clique-width
- The neighbourhood number of a graph
- Neighborhood perfect graphs
- Strong tree-cographs are Birkhoff graphs
- Depth-first search and the vertex cover problem
- Linear algorithms on recursive representations of trees
- Modular decomposition and transitive orientation
- Neighbourhood-perfect line graphs
- On semi-\(P_ 4\)-sparse graphs
- On computing a longest path in a tree
- The complexity of first-order and monadic second-order logic revisited
- Algorithmic aspects of clique-transversal and clique-independent sets
- Linear time solvable optimization problems on graphs of bounded clique-width
- New results on induced matchings
- On a property of the class of n-colorable graphs
- Efficient and Practical Algorithms for Sequential Modular Decomposition
- Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- A Fast Algorithm for the Decomposition of Graphs and Posets
- On the Algorithmic Complexity of Total Domination
- Minimal non-neighborhood-perfect graphs
- Total Domination in Graphs
- Algorithmic Aspects of Neighborhood Numbers
- Transitiv orientierbare Graphen
