Том 20, номер 1, 2013 г., Стр. 3-11

УДК 519.718
Визинг В. Г.
Полухроматическое число графа

Аннотация:
Для графов с непустым множеством рёбер введено понятие полухроматического числа. Доказано, что полухроматическое число отличается от половины хроматического числа не больше, чем на 1.
Библиогр. 5.

Ключевые слова: хроматическое число, полухроматическое число, инъективная раскраска.

Визинг Вадим Георгиевич ¹
1. ул. Варненская, 18/2, кв. 26, 65070 Одесса, Украина
е-mail: vizing@paco.net

Статья поступила 31 июля 2012 г.

Литература

[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982. - 416 c.

[2] Евстигнеев В. А., Касьянов В. Н. Толковый словарь по теории графов в информатике и программировании. - Новосибирск: Наука, 1999. - 288 с.

[3] Зыков А. А. Основы теории графов. - М: Вузовская книга, 2004. - 663 с.

[4] Jensen T. R., Toft B. Graph coloring problems. - New York: John Wiley & Sons, 1995. - 296 p.

[5] Robertson N., Sanders D., Seymour P. D., Thomas R. The four-colour theorem // J. Comb. Theory. Ser. B. - 1997. - Vol. 70. - P. 2–44