Independent set

Definition

Let $G$ be a graph. An independent set in $G$ is a set $S$ of vertices of $G$ such that no two vertices of $S$ are adjacent.

Remarks

A set is independent in $G$ if and only if it is a clique in the complement graph. A set $S$ is independent if and only if its complement in the vertex set is a vertex cover. The largest size of an independent set is the independence number $\alpha(G)$. Each colour class of a colouring is an independent set.

Explanations

L1 human

An independent set is a set of vertices with no edge between any two of them. In a conflict graph, it is a set of tasks that can all happen at the same time.