name: О хроматической определяемости некоторых классов трехдольных графов, хроматических инвариантах и решётках разбиений натуральных чисел
keyword_list: разбиения натуральных чисел полные многодольные графы хроматическая эквивалентность хроматическая определяемость
abstract: В данной работе все графы подразумеваются обыкновенными, то есть не содержащими петель и кратных ребер. Раскраской графа называется такое отображение из множества вершин графа в некоторое множество цветов, которое любым двум смежным вершинам ставит в соответствие различные цвета. Минимальное число цветов, в которое может быть раскрашен граф, называется хроматическим числом графа.
  Для натурального числа x и графа G через P(G, x) обозначим число раскрасок графа G в x цветов. Хорошо известно, что функция P(G, x) есть многочлен от переменной x. Этот многочлен называется хроматическим многочленом графа. 
  Два графа называются хроматически эквивалентными, если их хроматические многочлены совпадают. Нетрудно видеть, что это действительно отношение эквивалентности. Классы эквивалентности по этому отношению называются хроматическими классами. 
  Граф называется хроматически определяемым, если он изоморфен любому своему хроматически эквивалентному графу.
  Предположим, что каждому графу приписано некоторое число. Это число называется хроматическим инвариантом, если оно одинаковое для любых двух хроматически эквивалентных графов. Известно, что число вершин графа, число ребер, число треугольников в графе, хроматическое число графа являются хроматическими инвариантами. Также хроматическими инвариантами являются числа разбиений множества вершин на независимые множества, то есть множества попарно несмежных вершин.
  Граф называется t-дольным, если множество его вершин может быть разбито на t непересекающихся независимых множеств. Независимые множества назовем долями. Граф называется полным t-дольным, если любые две вершины из различных вершин смежны.
  Разбиением натурального числа n называется невозрастающая последовательность целых неотрицательных чисел, сумма элементов которой равна n. Длиной разбиения называется число положительных компонент.
  На множестве всех разбиений натурального числа n можно ввести отношение частичного порядка, известного как отношение доминирование. Брылавски показал, что разбиение натурального числа n образуют решетку относительно этого порядка. 
  Ясно, что размеры долей полного многодольного графа образуют разбиение числа вершин графа. Таким образом установлено взаимно-однозначное соответствие между полными t-дольными графами на n вершинах и разбиениями длины t натурального числа n.
  В работе установлена хроматическая определяемость полных трехдольных графов при выполнении одного из двух условий:
  1)	размеры двух наибольших долей отличаются на 1 и размер наименьшей доли не меньше 2;
  2)	размеры наибольшей и наименьшей долей отличаются не более чем на 5 и размер наименьшей доли не меньше 2.
  Так же в работе получены новые оценки хроматических инвариантов.
chairman_dissertation_council.name: Виталий
chairman_dissertation_council.surname: Бердышев
chairman_dissertation_council.patronymic: Иванович
chairman_dissertation_council.position: Главный научный сотрудник
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Академик
chairman_dissertation_council.wos_research_id: Q-1761-2017
chairman_dissertation_council.scopus_author_id: 55980665600
chairman_dissertation_council.rinc_id: 3668
chairman_dissertation_council.url: http://www.mathnet.ru/php/person.phtml?option_lang=rus&personid=19721
chairman_dissertation_council.orcid: 0000-0001-8057-5397
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Николай
organization_supervisor.surname: Лукоянов
organization_supervisor.patronymic: Юрьевич
organization_supervisor.position: Директор
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.45.17
rubrics.name: Теория графов
oecds.code: 01.01.PQ
oecds.name: MATHEMATICS
speciality_codes.name: Дискретная математика и математическая кибернетика
speciality_codes.code: 01.01.09
supervisors.fio: Баранский В.А.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
opponents.fio: Зенков В.И.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Математическая логика, алгебра и теория чисел
opponents.responsible_type: Оппонент
opponents.fio: Шалагинов Л.В.
opponents.scientific_degree: Кандидат физико-математических наук
opponents.speciality_code: Математическая логика, алгебра и теория чисел
opponents.responsible_type: Оппонент
protection_organization.short_name: ИММ УРО РАН
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ ИМ. Н.Н. КРАСОВСКОГО УРАЛЬСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК
protection_organization.ogrn: 1026604965177
protection_organization.supervisor_name: НИКОЛАЙ
protection_organization.supervisor_surname: ЛУКОЯНОВ
protection_organization.supervisor_patronymic: ЮРЬЕВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные бюджетные учреждения
author_organization.short_name: ФГАОУ ВО "УРФУ ИМЕНИ ПЕРВОГО ПРЕЗИДЕНТА РОССИИ Б.Н. ЕЛЬЦИНА", УРАЛЬСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ, УРФУ, УРАЛЬСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИМЕНИ ПЕРВОГО ПРЕЗИДЕНТА РОССИИ Б.Н. ЕЛЬЦИНА
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "УРАЛЬСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИМЕНИ ПЕРВОГО ПРЕЗИДЕНТА РОССИИ Б.Н. ЕЛЬЦИНА"
author_organization.ogrn: 1026604939855
author_organization.supervisor_name: ВИКТОР
author_organization.supervisor_surname: КОКШАРОВ
author_organization.supervisor_patronymic: АНАТОЛЬЕВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные автономные учреждения