Neighborhood perfect graphs

DOI10.1016/0012-365X(86)90031-2zbMath0602.05053OpenAlexW2019034047MaRDI QIDQ1081622

Zsolt Tuza, Jenő Lehel

Publication date: 1986

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(86)90031-2

zbMATH Keywords

perfect graphchordal graphsinterval graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Related Items (26)

An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs ⋮ Neighbourhood-perfect line graphs ⋮ Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths ⋮ On edge perfectness and classes of bipartite graphs ⋮ Clique-perfectness and balancedness of some graph classes ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs ⋮ Approximating weighted neighborhood independent sets ⋮ On some graph classes related to perfect graphs: a survey ⋮ Variations of maximum-clique transversal sets on graphs ⋮ Algorithmic aspects of clique-transversal and clique-independent sets ⋮ Variations of \(Y\)-dominating functions on graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs ⋮ An Efficient Algorithm for Helly Property Recognition in a Linear Hypergraph ⋮ Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs ⋮ Restricted unimodular chordal graphs ⋮ Distance-hereditary graphs are clique-perfect ⋮ Unnamed Item ⋮ Thek-neighbourhood-covering problem on interval graphs ⋮ Clique-perfectness of complements of line graphs ⋮ Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs ⋮ Block duplicate graphs and a hierarchy of chordal graphs ⋮ On balanced graphs ⋮ Characterization and recognition of Helly circular-arc clique-perfect graphs ⋮ Minimum r-neighborhood covering set of permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Graphs whose neighborhoods have no special cycles
• Characterizations of strongly chordal graphs
• The line neighbourhood number of a graph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Trivially perfect graphs
• A characterisation of rigid circuit graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Representations of chordal graphs as subtrees of a tree
• Khachiyan’s algorithm for linear programming
• Algorithmic Aspects of Vertex Elimination on Graphs
• A Note on "The Comparability Graph of a Tree"

This page was built for publication: Neighborhood perfect graphs