Abstract
A bull is the (self-complementary) graph with nodesa, b, c, d, e and edgesab, ac, bc, bd,ce. A star cutset in a graph G is a set C of nodes such thatG-C is disconnected, and such that some node inC is adjacent to all remaining nodes inC. A graph is called unbreakable if it has more than two nodes and if neither the graph nor its complement has a star cutset.
Hayward defined a graphG to be murky if neitherG nor its complement contains a chordless cycle with five nodes or a chordless path with six nodes. We prove that most unbreakable murky graphs are bull-free. This leads, via a result of Chvátal and Sbihi, to a shortening of Hayward’s proof that murky graphs are perfect.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chvátal, V. (1985): Star Cutsets and Perfect Graphs, J. Comb. Theory Sir.B 39, 189–199
Chvátal, V., N. Sbihi, (1987): Bull-free Berge graphs are perfect, Graphs and Combinatorics3, 127–139
Hayward, R.B. (1990): Murky graphs, J. Comb. Theory Sir.B 49, 200–235
König, D. (1916): Uber Graphen und ihre Anwendung auf Determinanten-Theorie und Mengenlehre, Math. Ann.77, 453–465
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hertz, A. Most unbreakable murky graphs are bull-free. Graphs and Combinatorics 9, 173–175 (1993). https://doi.org/10.1007/BF02988303
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02988303