\input zb-basic
\input zb-ioport
\iteman{io-port 00897353}
\itemau{Hartnell, Bert; Plummer, Michael D.}
\itemti{On 4-connected claw-free well-covered graphs.}
\itemso{Discrete Appl. Math. 64, No.1, 57-65 (1996).}
\itemab
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.
\itemrv{S.L.Bezrukov (Paderborn)}
\itemcc{}
\itemut{connected graph; greedy algorithm; independent set; recognition; well-covered graphs; characterization}
\itemli{doi:10.1016/0166-218X(94)00117-V http://www.elsevier.com/locate/dam}
\end