Most unbreakable murky graphs are bull-free

DOI10.1007/BF02988303MaRDI QIDQ2366956zbMATH OpenOpenAlexFDO

Authors Alain Hertz

Publication date 11 August 1993

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02988303

zbMATH Keywords

bull graphbull-freechordless pathmurky graphperfectunbreakable

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Review text

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.

Recommendations

• Murky graphs
• Every graph admits an unambiguous bold drawing
• Every graph admits an unambiguous bold drawing
• More reliable graphs are not always stronger
• scientific article; zbMATH DE number 4172999
• Yet another look at the Gray graph
• Some disgraceful graphs
• Most graphs are knotted
• scientific article; zbMATH DE number 7714497

Cites work

• Bull-free Berge graphs are perfect
• Murky graphs
• Star-cutsets and perfect graphs

Cited in

(2)

• Murky graphs
• A NEW CHARACTERIZATION OF UNBREAKABLE GRAPHS

This page was built for publication: Most unbreakable murky graphs are bull-free

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366956)