О сложности построения 3-раскраски планарных графов с короткими гранями

Задача о вершинной 3-раскраске для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известно, что эта задача является NP-полной в классе планарных графов и что она становится полиномиально разрешимой для плоских триангуляций — планарных графов, у которых все грани (включая и внешнюю) являются треугольниками. Известно также, что она является NP-полной в классе планарных графов со степенями всех вершин не более чем 4, но становится разрешимой за линейное время в классе графов с максимильной степенью вершин не более чем 3. Поэтому интересен вопрос о поиске порога на значения длин граней и максимальной степени вершин планарных графов, при переходе через который для задачи о вершинной 3-раскраске полиномиальная разрешимость меняется на NP-полноту. В данной работе дается ответ на этот вопрос и доказывается NP-полнота задачи о вершинной 3-раскраске в классе планарных графов, гранями которых являются только треугольники и четырехугольники, с максимальной степенью вершин не более чем 5.