Раскраска графа: различия между версиями

Основная проблема в контексте приближенной раскраски графов касается значительного разрыва между задачами, известными как сложные, и задачами, которые могут быть решены за полиномиальное время. Случай с константным значением <math>\chi (G) \; </math> особенно интересен, поскольку наилучшие известные верхние границы коэффициента аппроксимации являются полиномиальными, тогда как нижние границы константны. Что касается парадигмы векторной раскраски, большинство результатов раздела «Основные результаты» используют при доказательстве самую слабую форму векторной раскраски <math>\overrightarrow{\chi} (G) \; </math>, тогда как стоит также рассматривать более сильные релаксации – такие как <math>\overrightarrow{\chi}_2 (G) \; </math> и <math>\overrightarrow{\chi}_3 (G) \; </math>. Было бы очень интересно улучшить вышеприведенные алгоритмические результаты, используя более сильные релаксации, а также соответствующий анализ ограничений этих релаксаций.