Хроматичность полных расщепленных графов
https://doi.org/10.22405/2226-8383-2024-25-2-208-221
Аннотация
Соединение нулевого графа 𝑂𝑚 и полного графа 𝐾𝑛, 𝑂𝑚 + 𝐾𝑛 = 𝑆(𝑚, 𝑛), называется полным разделенным графом. В этой статье мы характеризуем хроматическую уникальность, определяем хроматический номер списка и характеризуем уникальную раскрашиваемость списка для полного графа разделения 𝐺 = 𝑆(𝑚, 𝑛). Мы докажем, что 𝐺 хроматически уникален тогда и только тогда, когда 1 𝑙𝑒𝑚 𝑙𝑒2, 𝑐ℎ(𝐺) = 𝑛 + 1, 𝐺 является уникальным раскрашиваемым графом с 3-списком тогда и только тогда, когда 𝑚 ⩾ 4,
𝑛 ⩾ 4 и 𝑚 + 𝑛 ⩾ 10, 𝑚(𝐺) ⩽ 4 на каждые 1 ⩽ 𝑚 ⩽ 5 и 𝑛 ⩾ 6. Также доказано некоторое свойство графа 𝐺 = 𝑆(𝑚, 𝑛), когда он представляет собой 𝑘-листовой раскрашиваемый граф.
Список литературы
1. Бехзад, М. Графы и хроматическое число // Докторская диссертация (Мичиганский го-
2. сударственный университет), 1965.
3. Бехзад М., Чартранд Г. // Введение в теорию графов, Эллин и Бэкон, Бостон, 1971.
4. Бехзад М., Чартранд Г., Купер Дж. Числа раскраски полных графов // Журнал Лон-
5. донского мат. общ., 42 (1967), С. 226 - 228.
6. Биркгоф Г. Д. Детерминантная формула для числа способов раскраски карты // Анналы
7. математики, 14 (2), (1912), С. 42–46.
8. Бонди Дж. А., Мурти У. С. Р. Теория графов с приложениями // МакМиллан, 1976.
9. Брандстадт A., Хаммер П. Л., Ле В. Б., Лозин В.В. Бисплитные графы // Дискретная
10. математика, 299 (2005), С. 11–32.
11. Чен Б. Л., Фу Х. Л, Ко М. Т. Общее хроматическое число и хроматический индекс расщепленных графов // Журнал комбинаторной математики и комбинаторных вычислений, 17 (1995), С. 137–146.
12. Брент Ф. Расширения хроматического многочлена и логконкавиальность // Транс амери-
13. канская математическая школа, 332 (1992), С. 729 – 756.
14. Буркард Р. Э.,Хаммер П. Л. Замечание о гамильтоновых расщепленных графах // Жур-
15. нал комбинаторной теории. Серия A., Вып. 28 (1980), С. 245–248.
16. Чао К. Ю., Уайтхед Э. Г. мл. О хроматической эквивалентности графов // Теория и
17. приложения графов, под ред. Й. Алави и Д.Р. Лика, Конспекты лекций по математике,
18. (1978), С. 121 -131.
19. Чватал В., Хаммер П. Л. Агрегация неравенств в целочисленном программировании //
20. Анналы дискретной математики, 1 (1977), С. 145–162.
21. Дистель Р. Теория графов // Шпрингер - Верлаг, Нью-Йорк, 2000.
22. Диниц Дж. Х., Мартин У. Дж. Полином обусловленности уникально списочного раскрашиваемого графа // Австралазийский журнал по комбинаторике, 11 (1995), С. 105–115.
23. Фолдес С., Хаммер П. Л. Разделенные рафы // Восьмая Юго-Восточная конферен-
24. ция по комбинированию., Теория графов и вычисления (Университет штата Луизиана,
25. Батон-Руж, Ла., 1977), С. 311–315. Конгресс Нумерантиум, № XIX, Утилита Математи-
26. ка.,Виннипег, штат Мэн., 1977.
27. Фолдес С., Хаммер П. Л. О классе графов, порождающих матроиды // Комбинаторика
28. (Успехи Пятого венгерского коллоквиума, Кестхей 1976) vol. 1, С. 331–352. Математиче-
29. ские интервью в Обществе Яноша Больяи 18, Северная Голландия, Амстердам - Нью-
30. Йорк, 1978.
31. Гебле М., Махмудян Э.С. Об уникальном списке раскрашиваемых графов // Арс Комбинатория, 59 (2001), С. 307–318.
32. Хе У. Дж., Ван Ю. Н., Шен Ю.Ф., Ма Х. О свойстве M (3) некоторых полных многочаст-
33. ных графов // Австралазийский журнал комбинаторики, в печати.
34. Хендерсон П. Б., Залкштейн Ю. Теоретико-графовая характеристика класса синхронизирующих 𝑃𝑉_𝑐ℎ𝑢𝑛𝑘 примитивов // СИАМ Журнал по вычислительной технике, 6 (1977), С. 88–108.
35. Хишам А. Х., Хешам Эль-Ревини. Распределение задач в распределенных системах: модель расщепленного графа // Журнал комбинаторной математики и комбинаторных вычислений, 14 (1993), С. 15–32.
36. Ле Сюань Хунг, Листовое хроматическое число и хроматическая уникальность графа
37. (𝐾_𝑟)^2 +𝑂_𝑘 // Математические Подборки, Национальный университет Трухильо, Вып 06(01): 26 - 30 (2019).
38. Ле Сюань Хунг, Раскраски графа (𝐾_𝑚)^2 +𝐾_𝑛 // Журнал Сибирского федерального университета. Математика & Физика, 2020, 13(3), С. 297 – 305.
39. Ле Сюань Хунг, Хроматичность соединения дерева и нулевого графа, Прикладная дискретная математика 2020, Вып. 50, С. 93 – 101.
40. Ле Сюань Хунг, Уникальная раскрашиваемость списка графа 𝐾𝑛
41. +𝐾𝑟, Прикладная Дискретная Математика 2022, Вып. 55, С. 88 – 94.
42. Ле Сюань Хунг, 2022, Уникальная списочная раскрашиваемость полных трехсторонних графов, Чебышевский сборник, Т. 23, № 2, С. 170-178.
43. Ко К. М., Тео К. Л. Поиск уникальных по цвету графов // Графы и комбинаторика, 6
44. (1990) 259 – 285.
45. Ко К. М., Тео К. Л., Поиск хроматически уникальных графов II // Дискретная матема-
46. тика,172 (1997), С. 59 – 78.
47. Кратш Д., Лехель Й., Мюллер Х. Жесткость, гамильтоничность и расщепленные графы // Дискретная математика, 150 (1996), С. 231–245.
48. Liu R. Y. Новый метод нахождения хроматического многочлена графа и его приложения // Кэсюэ Тунбао, 32 (1987), С. 1508 – 1509.
49. Махдиан М., Махмудян Э.С. Характеристика уникально 2-списочных раскрашиваемых графов // Арс Комбинатория, 51 (1999), С. 295–305.
50. Пимюллер Дж. Необходимые условия для гамильтонова расщепления графов // Дискретная математика, 54 (1985), С. 39–47.
51. Пелед Ю. Н. Регулярные булевы функции и их политопы. Глава VI // Докторская дис-
52. сертация, Университет Ватерлоо, кафедра комбинаторики и оптимизации, 1975.
53. Рид Р. С. Введение в хроматические многочлены // Журнал комбинаторной теории. Серия А, 4 (1968), С. 52 – 71.
54. Шэнь Ю. Ф., Ван Ю. Н. В уникальном списке раскрашиваемых полных многогранных
55. графиков // Арс Комбинатория, 88 (2008), С. 367-377.
56. Нго Дак Тан, Ле Ван Хонг. Гамильтоновы циклы в расщепленных графах с большой
57. минимальной степенью // Обсуждение математической теории графов 24 (2004), С. 23 –
58.
59. Нго Дак Тан, Ле Ван Хонг. Об условии Беркарда-Хаммера для гамильтоновых расщепленных графов // Дискретная математика 296 (2005), С. 59 – 72.
60. Нго Дак Тан, Ле Ван Хонг. О раскрасках расщепленных графов // Вьетнамский Математический Журнал, том 31, номер 3, 2006, С. 195 – 204.
61. Визинг В. Г. Об оценке хроматического класса 𝑝-графа // Дискретный анализ, 3 (1964)
62. –30. (In Russian).
63. Ван И., Ван Ю., Чжан Х. Некоторые выводы об уникальных 𝑘-листовых раскрашиваемых полных многочастичных графах // Journal of Applied Mathematics, pp. 5, ID 380 861 (2013).
64. DOI http://dx.doi.org/10.1155/2013/380861
65. Ван И., Шен И., Чжэн Г., Хе В. Об уникально 4-списочных раскрашиваемых полных
66. многочастичных графах // Арс Комбинатория, vol.93, 2009, С. 203-214.
67. Уилсон Р. Дж. Введение в теорию графов // Лонгман групп, Лондон (1975).
Рецензия
Для цитирования:
Хонг В. Хроматичность полных расщепленных графов. Чебышевский сборник. 2024;25(2):208-221. https://doi.org/10.22405/2226-8383-2024-25-2-208-221
For citation:
Hung X. The chromaticity of complete split graphs. Chebyshevskii Sbornik. 2024;25(2):208-221. (In Russ.) https://doi.org/10.22405/2226-8383-2024-25-2-208-221
Просмотров:
265
Послать статью по эл. почте 