Murky graphs (Q1101470)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Murky graphs |
scientific article; zbMATH DE number 4047776
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Murky graphs |
scientific article; zbMATH DE number 4047776 |
Statements
Murky graphs (English)
0 references
1990
0 references
A graph is murky if neither the graph nor its complement contains a chordless cycle with five vertices or a chordless path with six vertices. A star cutset in a graph G is a set C of vertices, such that G - C is disconnected, and such that some vertex in C is adjacent to all remaining vertices in C. A graph is called unbreakable if it has more than two vertices and if neither the graph nor its complement has a star cutset. The main result is a proof that murky graphs are perfect. A characterization of unbreakable murky graphs is also presented.
0 references
chordless cycle
0 references
chordless path
0 references
star cutset
0 references
murky graphs
0 references
perfect graphs
0 references
unbreakable graphs
0 references
