An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of $$K_4$$ (the complete graph on four vertices). A wheel is a graph that consists of a chordless cycle, together with a vertex that has at least three neighbors in the cycle. A graph is {ISK4,wheel}-free if it has no ISK4 and does not contain a wheel as an induced subgraph. We give an $$O(|V(G)|^7)$$ -time algorithm to compute the maximum weight of a stable set in an input weighted {ISK4,wheel}-free graph G with non-negative integer weights.

We prove that any graph $G$ of minimum degree greater than $2k^2-1$ has a $(k+1)$-connected induced subgraph $H$ such that the number of vertices of $H$ that have neighbors outside of $H$ is at most $2k^2-1$. This generalizes a classical result of Mader, which states that a high minimum degree implies the existence of a highly connected subgraph. We give several variants of our result, and for each of these variants, we give asymptotics for the bounds. We also compute optimal values for the case when $k=2$. Alon, Kleitman, Saks, Seymour, and Thomassen proved that in a graph of high chromatic number, there exists an induced subgraph of high connectivity and high chromatic number. We give a new proof of this theorem with a better bound.

A graph $G$ is perfect if for every induced subgraph $H$ of $G$, the chromatic number of $H$ equals the size of the largest complete subgraph of $H$. A bull is a graph on five vertices consisting of a triangle and two vertex-disjoint pendant edges. A graph is said to be bull-free if none of its induced subgraphs is a bull. In [SIAM J. Discrete Math., 18 (2004), pp. 226--240], de Figueiredo and Maffray gave polynomial time combinatorial algorithms that solve the following four optimization problems for weighted bull-free perfect graphs with integer weights: the maximum weighted clique problem; the maximum weighted stable set problem; the minimum weighted coloring problem; and the minimum weighted clique covering problem. In this paper, we give faster combinatorial algorithms that solve the same four problems. The running time of our algorithms for finding a maximum weighted clique and a maximum weighted stable set in a weighted bull-free perfect graph with integer weights is $O(n^6)$, and the running time of our algorithms for finding a minimum weighted coloring and a minimum weighted clique covering in such a graph is $O(n^8)$, where $n$ is the number of vertices of the input graph.