Marked Graphs

Why

Sometimes it is convenient to partition the set of veritices of a graph.

Definition

Given a directed graph $G = (V, E)$, a marking (or coloring) of $G$ is a partition $P$ of $V$. A marked graph (or colored graph) is a pair $(G, M)$ where $M$ is a marking for $G$.