๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Neighborhood perfect graphs

โœ Scribed by J Lehel; Zs Tuza

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
595 KB
Volume
61
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

The notion of neighborhood perfect graphs is introduced here as follows. Let G be a graph, ~N(G) denote the maximum number of edges such that no two of them belong to the same subgraph of G induced by the (closed) neighborhood of some vertex; let PN(G) be the minimum number of vertices whose neighborhood subgraphs cover the edge set of G. Then G is called neighborhood perfect if PN(G') = CrN(G' ) holds for every induced subgraph G' of G. It is expected that neighborhood perfect graphs are perfect also in the sense of Berge. We characterize here those chordal graphs which are neighborhood perfect. In addition, an algorithm to compute PN(G) = ON(G) is given for interval graphs.

๐Ÿ“œ SIMILAR VOLUMES

On perfect neighborhood sets in graphs
On perfect neighborhood sets in graphs
โœ Gerd H. Fricke; Teresa W. Haynes; Sandra Hedetniemi; Stephen T. Hedetniemi; Mich ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 279 KB
Split-Neighborhood Graphs and the Strong
Split-Neighborhood Graphs and the Strong Perfect Graph Conjecture
โœ F. Maffray; M. Preissmann ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 649 KB

We introduce the class of graphs such that every induced subgraph possesses a vertex whose neighbourhood can be split into a clique and a stable set. We prove that this class satisfies Berge's strong perfect graph conjecture. This class contains several well-known classes of (perfect) graphs and is

Neighborhood subtree tolerance graphs
Neighborhood subtree tolerance graphs
โœ Eric Bibelnieks; P.M. Dearing ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 906 KB
A generalization of perfect graphs?i-per
A generalization of perfect graphs?i-perfect graphs
โœ Cai, Leizhen; Corneil, Derek ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 1003 KB

Let i be a positive integer. We generalize the chromatic number x ( G ) of G and the clique number w(G) of G as follows: The i-chromatic number of G , denoted by x Z ( G ) , is the least number k for which G has a vertex partition V,, V,, . . . , Vk: such that the clique number of the subgraph induc