Граф называется двудольным, если его вершины можно разбить на две группы (называемые долями) так, чтобы все рёбра (или дуги) были между различными долями. Паросочетанием называется такой набор рёбер графа, что каждая вершина графа является концом не более одного ребра из набора. Паросочетание называется совершенным, если каждая вершина является концом ровно одного ребра паросочетания. Раскраска вершин графа называется правильной, если никакие две вершины одного цвета на соединены ребром. Граф называется $k$-дольным, если правильная раскраска его вершин возможна $k$ цветами и не менее.