We study the problem where a robot has to pick up items of different sizes which are stored
along a corridor. A natural requirement is that the items have to be collected in decreasing …

This paper deals with the characterization and the recognition of graph classes. A popular
way to characterize a graph class is to list a minimal set of forbidden induced subgraphs …

Ordinary colourings of cographs are well understood; we focus on more general colourings,
known as matrix partitions. We show that all matrix partition problems for cographs admit …

In this work, we focus on the class of P4-sparse graphs, which generalizes the well-known
class of cographs. We consider the problem of verifying whether a P4-sparse graph is a (k …

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split
graphs and complements of bipartite graphs. A graph is (s, k)-polar if there exists a partition …

A graph G is well-covered if every maximal independent set of G is maximum. A (k, ℓ)-
partition of a graph G is a partition of its vertex set into k independent sets and ℓ cliques. A …

Let C be a class of graphs. A graph G=(V, E) is C-probe if V (G) can be partitioned into two
sets: non-probes N and probes P, where N is an independent set and new edges may be …

Let CC be a class of graphs. A graph G=(V, E) G=(V, E) is CC–probe if V (G) can be
partitioned into two sets: non-probes NN and probes PP, where NN is an independent set …

Abstract A (k, ℓ)(k, ℓ)-partition of a graph G is a partition of its vertex set into k independent
sets and ℓ ℓ cliques. A graph is (k, ℓ)(k, ℓ) if it admits a (k, ℓ)(k, ℓ)-partition. A graph is well …

Sparse-dense partitions was introduced by Feder, Hell, Klein, and Motwani [STOC 1999,
SIDMA 2003] as a tool to solve partitioning problems. In this paper, the following result …