List partitions generalize list colorings and list homomorphisms.(We argue that they may be
called list" semihomomorphisms.") Each symmetric matrix M over 0, 1,* defines a list partition …

Can the vertices of a graph $ G $ be partitioned into $ A\cup B $, so that $ G [A] $ is a line-
graph and $ G [B] $ is a forest? Can $ G $ be partitioned into a planar graph and a perfect …

We consider the following generalization of split graphs: A graph is said to be a (k, ℓ)-graph
if its vertex set can be partitioned into k independent sets and ℓ cliques.(Split graphs are …

We examine the effect of bounding the diameter for a number of natural and well-studied
variants of the COLOURING problem. A colouring is acyclic, star, or injective if any two …

An undirected graph G=(V, E) is a bisplit graph if its vertex set can be partitioned into a
stable set and a complete bipartite graph. We provide an O (| V|| E|) time recognition …

We consider the problem of partitioning the node set of a graph into p cliques and k stable
sets, namely the (p, k)-coloring problem. Results have been obtained for general graphs …

Abstract The Near-Bipartiteness problem is that of deciding whether or not the vertices of a
graph can be partitioned into sets A and B, where A is an independent set and B induces a …

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,...,A_k, where it may be specified that A_i induces …

For a given graph G, if the vertices of G can be partitioned into an independent set and an
acyclic set, then we call G a near-bipartite graph. This paper studies the recognition of near …

A graph G is (k, l) if its vertex set can be partitioned into at most k independent sets and l
cliques. The (k, l)-Graph Sandwich Problem asks, given two graphs G1=(V, E1) and G2=(V …