Neighbourhood-Perfect Line Graphs |
| |
Authors: | Jenö Lehel† |
| |
Affiliation: | 1. Department of Mathematics, College of Arts and Sciences, University of Louisville, KY40292, Louisville, USA
|
| |
Abstract: | We show that the line graph of any balanced hypergraph is neighbourhood-perfect. This result is a hypergraphic extension of a recent theorem in [GKLM] saying that the line graphs of bipartite graphs are neighbourhood-perfect. The note contains also a graphical extension of the same theorem: the characterization of all graphs with neighbourhood-perfect line graph. The proof relies on a characterization of neighbourhood-perfect graphs among line graphs in terms of forbidden induced subgraphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|