Murky graphs
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3889564 (Why is no real title available?)
- scientific article; zbMATH DE number 3060538 (Why is no real title available?)
- Normal hypergraphs and the perfect graph conjecture
- On a property of the class of n-colorable graphs
- On sources in comparability graphs, with applications
- Star-cutsets and perfect graphs
- Topics on perfect graphs
- Weakly triangulated graphs
Cited in
(9)- Locally perfect graphs
- On minimal imperfect graphs without induced P₅
- Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance
- On the stable set problem in special \(P_{5}\)-free graphs
- Discs in unbreakable graphs
- Most unbreakable murky graphs are bull-free
- Classes of perfect graphs
- scientific article; zbMATH DE number 4079463 (Why is no real title available?)
- Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
This page was built for publication: Murky graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101470)
