Множество C вершин графа G такое, что любой порождённый подграф графа G, изоморфный графу из X, содержит хотя бы одну вершину из С, называется вершинным покрытием графа G относительно X, или просто его X-покрытием. Иными словами, X-покрытие графа G — это такое множество вершин C, что G/С ∈ Free (X).
Задача об X-покрытии (X-COVER) состоит в том, чтобы найти X-покрытие графа наименьшего размера.
Граф G называется кёниговым относительно X, если в любом его порождённом подграфе H размер наибольшей X-упаковки равен размеру наименьшего X-покрытия.
В докладе будет дан обзор задач об упаковке и покрытии относительно различных классов, а также будет приведено описание некоторых классов кёниговых графов.
