Title of article
Loose vertices in C4-free Berge graphs Original Research Article
Author/Authors
I. Parfenoff، نويسنده , , F. Roussel، نويسنده , , I. Rusu، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2002
Pages
24
From page
137
To page
160
Abstract
Following Maire (Graphs Combin. 10 (3) (1994) 263) we call a loose vertex a vertex whose neighbourhood induces a P4-free graph, and we show that every C4-free Berge graph G which is not a clique either is breakable (i.e. G or Ḡ has a star-cutset) or contains at least two non-adjacent loose vertices. Consequently, every minimal imperfect C4-free graph has loose vertices.
Keywords
Berge graph , Perfect graph , Lexicographic breadth-first search
Journal title
Discrete Mathematics
Serial Year
2002
Journal title
Discrete Mathematics
Record number
949375
Link To Document