• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

О пересечении и симметрической разности семейств граничных классов графов для задач о раскраске и о хроматическом числе

Дискретная математика. 2012. Т. 24. № 2. С. 75-78.

В данной работе исследуются семейства граничных классов для задач о вершинной k-раскраске и о хроматическом числе. Указано континуальное семейство классов графов, являющихся граничными одновременно для первой задачи при k=3 и для второй. Для любого k>3 выявлено континуальное семейство граничных классов для первой задачи, не являющихся граничными для второй. Для задачи о хроматическом числе найден граничный класс, не являющийся граничным для задачи о вершинной k-раскраске ни при каком k.