On 4-connected claw-free well-covered graphs (Q1917239): Difference between revisions

A connected graph is called well covered, if the greedy algorithm for constructing an independent set always results in a maximum independent set. Although the recognition of such graphs is known to be co-NP-complete, for some particular classes of well-covered graphs there exist polynomial recognition algorithms. Among such results is a characterization of claw-free well-covered graphs having no 4-cycles. In contrast to this the authors found a characterization of some classes, whose graphs contain 4-cycles: the 4-connected 4-regular claw-free well-connected graphs and the 4-connected planar such graphs. It is shown that the last class consists of precisely 5 graphs.