Most unbreakable murky graphs are bull-free (Q2366956): Difference between revisions

The author proves that all unbreakable murky graphs with the exception of two are bull-free. This result implies that all murky graphs are perfect. A bull graph is a self-complementary graph on 5 vertices distinct from \(C_ 5\) (the cycle on 5 vertices). The notion of a murky graph was introduced by R. B. Hayward as a graph \(G\) such that neither \(G\) nor its complement \(\overline G\) contains chordless \(C_ 5\) or \(P_ 6\) (path with 6 vertices). A graph \(G\) is called unbreakable if neither \(G\) nor \(\overline G\) contains a cutset with spanning star graph.