An independent set of a graph is a collection of vertices such that the induced subgraph consists of disconnected vertices. The maximum possible cardinality of an independent set is then called the independence number of the graph.

For $k$ a positive integer, we define a $k$-independent set of a graph to be a collection of vertices such that the induced subgraph consists of components with $k$ vertices or fewer. (In particular, a $1$-independent set is the same as an independent set.) We then define the $k$-independence number of a graph to be the maximum possible cardinality of a $k$-independent set.

Have these notions of $k$-independent sets and $k$-independence numbers been studied before? If so, what names do they go by in the literature?

(Note: the term "$k$-independence number" does appear in the literature, but it asks for the induced subgraphs to have maximum degree at most $k$, rather than at most $k$ vertices.)


1 Answer 1


There is a version of graph colouring where instead of insisting that each colour class is an independent set, you require each colour class to be a $c$-independent set. This is known as a colouring with clustering $c$. The clustered chromatic number of a class of graphs is the minimum $k$ such that for some integer $c$, every graph in the class is $k$-colourable with clustering $c$. Clustered chromatic number has received quite a lot of attention recently. For example, van den Heuvel and Wood proved that every $K_t$-minor free graph is $(2t-2)$-colourable with clustering at most $\lceil\frac{1}{2}(t-2) \rceil$. Note that the analogous statement for the chromatic number is the linear Hadwidger's conjecture, and is still open.

See this survey by David Wood for more information. The survey also discusses colourings where each colour class has bounded maximum degree. These are known as defective colourings.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .