Обычно граф определяется как
упорядоченная пара из двух множеств — множества вершин этого графа (они же узлы) и множества связей этого графа (они же рёбра, дуги = ориентированные рёбра).
Г := < В , Р >

Мне же нужен не простой граф, а граф с вершинами разных типов (видимо это называется "окрашенные вершины").

И не только граф, но и алгоритм поиска в направленном графе
подграфа с заданной раскраской (в частном случае не подграфа, а цепочки).

поиск цепочки в окрашенном направленном ациклическом графе

Вы скажете — сядь и подумай. Переборами, переборами.
Перебираем все вершины графа, для каждой смотрим — есть ли исходящий из этой вершины путь, полностью совпадающий с цепочкой.

Мне в таком решении не нравятся два момента:
1) при добавлении новой вершины (со связями) в граф надо будет всё пересматривать, а это излишне трудоёмко.
2) вообще полный перебор выглядит излишне трудоёмким. Есть же вдохновляющий алгоритм Кнута-Морриса-Пратта, в котором количество действий снижается (у них там, правда, не граф и цепочка, а просто две цепочки).

Вы скажете — надо тебе инкрементально, прикладывай цепочку разными узлами к нововставленной в граф вершине и проверяй наличие обоих хвостов цепочки в графе. Но и тут, мне кажется, можно сэкономить, если граф предварительно дополнительно разметить.

Как нужный мне алгоритм называется и как его искать?