Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs

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

zbMATH Keywords

forbidden induced subgraphsrecognition algorithmstree-cographsco-bipartite graphs\(P_4\)-tidy graphsneighborhood-perfect graphs

Mathematics Subject Classification ID

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