Задачи раскрашивания одни из самых важных в теории графов. Мы говорим о правильных раскрашиваниях, то есть таких, где смешанные вершины раскрашенные в разные цвета. Задача раскрашивания триангуляций упрощается благодаря тому, что правильные триангуляции легко генерируются, а каждая правильная триангуляция имеет простой код. Так как правильная триангуляция либо 3-раскрашиваема, либо 4-раскрашиваема, то задача формулируется так: для каких наборов (k,l,m,n) существуют правильные раскрашивания...Подробнее

Описать «тонкую» структуру раскраски правильных триангуляций

Отчёт

Отчёт, препринт

Компьютерные системы, поддерживающие работу с графами

1. D. Poulalhon and G. Schaeffer. Optimal coding and sampling of triangulations. Algorithmica, 2006, 46(3-4), 505-527.