9.7. Замечания, касающиеся литературы

Общие ссылки на литературу, охватывающую тему данной главы, — это работы [9.2, 9.6, 9.16].

Классический результат теории графов, принадлежащий Турану [9.17], определяет, какое минимальное число ребер должен содержать граф на вершинах с числом независимости не более k (упражнение 9.2). См. работу [9.18]. Этот результат является отправной точкой в ветви теории графов, называемой теорией экстремальных графов. Книга Болобаша [9.15] посвящена исключительно изучению задач, связанных с экстремальными графами. Характеристики экстремальных графов образуют основу проектирования сетей связи с заданными свойствами надежности и уязвимости. См. работы

Применение числа независимости в теории информации можно найти в работах [9.2] (гл. 16), [9.24] (гл. 9), [9.25].

Рид [9.26] дал прекрасный обзор результатов по хроматическим полиномам. См. также работы [9.27-9.29]. Лю [9.24] обсуждает применение раскраски при разложении графов на планарные подграфы. Эта задача возникает при проектировании печатных плат. Применение раскраски к задачам составления расписания можно найти в работе [9.30], а алгоритм раскраски — в работе [9.31].

Множество вершин D графа G называется доминирующим, если любая вершина, не входящая в множество D, смежна с вершиной того же множества. Обзор результатов, касающихся доминирующих множеств, можно найти в работе [9.32]. Экстремальные результаты, касающиеся доминирующих множеств, даны в работе [9.33].