In this paper, we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance-graph (which has
vertices) is revealed in
clusters, 2 ≤
. We first focus on the on-line version of the following problem: finding a maximum-weighted subgraph satisfying some hereditary property. Then, we deal with the particular case of the independent set. For all these problems, we are interested in two types of results: the competitivity ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problems and for the quality of algorithms developed to solve them.