The sun is the graph obtained from a cycle of length even and at least six by adding edges to make the even-indexed vertices pairwise adjacent. Suns play an important role in the study of strongly chordal graphs. A graph is chordal if it does not contain an induced cycle of length at least four. A graph is strongly chordal if it is chordal and every even cycle has a chord joining vertices whose distance on the cycle is odd. Farber proved that a graph is strongly chordal if and only if it is chordal and contains no induced suns. There are well known polynomial-time algorithms for recognizing a sun in a chordal graph. Recently, polynomial-time algorithms for finding a sun for a larger class of graphs, the so-called HHD-free graphs (graphs containing no house, hole, or domino), have been discovered. In this paper, we prove the problem of deciding whether an arbitrary graph contains a sun is NP-complete.

The k-partition problem is as follows: Given a graph G and a positive integer k, partition the vertices of G into at most k parts $A_1, A_2, \ldots , A_k$, where it may be specified that $A_i$ induces a stable set, a clique, or an arbitrary subgraph, and pairs $A_i, A_j (i \neq j)$ be completely nonadjacent, completely adjacent, or arbitrarily adjacent. The list k-partition problem generalizes the k-partition problem by specifying for each vertex x, a list $L(x)$ of parts in which it is allowed to be placed. Many well-known graph problems can be formulated as list k-partition problems: e.g., 3-colorability, clique cutset, stable cutset, homogeneous set, skew partition, and 2-clique cutset. We classify, with the exception of two polynomially equivalent problems, each list 4-partition problem as either solvable in polynomial time or NP-complete. In doing so, we provide polynomial-time algorithms for many problems whose polynomial-time solvability was open, including the list 2-clique cutset problem. This also allows us to classify each list generalized 2-clique cutset problem and list generalized skew partition problem as solvable in polynomial time or NP-complete.

A graph is quasi‐triangulated if each of its induced subgraphs has a vertex which is either simplicial (its neighbors form a clique) or cosimplicial (its nonneighbors form an independent set). We prove that a graph G is quasi‐triangulated if and only if each induced subgraph H of G contains a vertex that does not lie in a hole, or an antihole, where a hole is a chordless cycle with at least four vertices, and an antihole is the complement of a hole. We also present an algorithm that recognizes a quasi‐triangulated graph in $O(nm)$ time.

Let ${\cal F}$ be a family of graphs. Two graphs G 1 = (V 1 ,E 1 ), G 2 =(V 2 ,E 2 ) are said to have the same ${\cal F}$-structure if there is a bijection $f: V_1 \rightarrow V_2$ such that a subset S induces a graph belonging to ${\cal F}$ in G 1 if and only if its image f(S) induces a graph belonging to ${\cal F}$ in G 2 . We characterize those graphs which have the same $\{P_3,\overline{P}_3\}$-structure, or the same $\{K_3,\overline{K}_3\}$-structure. This characterization shows that graph H is perfect if and only if it has the $\{P_3,\overline{P}_3\}$-structure of some perfect graph G. In proving the main result, we need and prove the following result, which is of independent interest: If a graph J is claw-free and co-claw-free, then either (i) J has at most nine vertices, or (ii) every component of J is a path or a hole, or (iii) every component of $\overline{J}$ is a path or a hole.

A graph is a split graph if its vertices can be partitioned into a clique and a stable set. A graph is a k-split graph if its vertices can be partitioned into k sets, each of which induces a split graph. We show that the strong perfect graph conjecture is true for 2-split graphs and we design a polynomial algorithm to recognize a perfect 2-split graph.