Том 22, номер 2, 2015 г., Стр. 63−72
УДК 519.174
А. В. Пяткин
Об интервальной (1, 1)-раскраске инциденторов интервально раскрашиваемых графов
Аннотация:
Граф назвается интервально раскрашиваемым, если существует такая правильная раскраска его рёбер, что для каждой вершины набор цветов, использованных для раскраски рёбер, примыкающих к ней, образует интервал. Подразбиением графа называется граф, полученный заменой каждого ребра путём длины 2. П. Петросян и Х. Хачатрян выдвинули гипотезу, что подразбиение любого интервально раскрашиваемого графа интервально раскрашиваемо. В настоящей работе приводится доказательство этой гипотезы.
Библиогр. 19.
Ключевые слова: интервальная раскраска, инцидентор, подразбиение графа.
DOI: 10.17377/daio.2015.22.454
Пяткин Артем Валерьевич 1,2
1. Институт математики им. С. Л. Соболева
пр. Коптюга, 4, 630090, Новосибирск, Россия
2. Новосибирский гос. университет
ул. Пирогова, 2, 630090 Новосибирск, Россия
e-mail: artem@math.nsc.ru
Статья поступила 2 июня 2014 г.
Исправленный вариант — 24 ноября 2014 г.
Литература
[1] Асратян А. С., Камалян Р. Р. Интервальные раскраски рёбер мультиграфа // Прикладная математика. Вып. 5. Ереван: Изд-во Ереван. ун-та, 1987. С. 25–34.
[2] Визинг В. Г. Интервальная раскраска инциденторов ориентированного мультиграфа // Дискрет. анализ и исслед. операций. Сер. 1. 2001. Т. 8, №2. С. 40–51.
[3] Визинг В. Г. Двудольная интерпретация ориентированного мультиграфа // Дискрет. анализ и исслед. операций. Сер. 1. 2002. Т. 9, №1. С. 27–41.
[4] Визинг В. Г. Интервальная раскраска инциденторов неориентированного мультиграфа // Дискрет. анализ и исслед. операций. Сер. 1. 2003. Т. 10, №1. С. 14–40.
[5] Визинг В. Г. Жёсткая раскраска инциденторов в неориентированных мультиграфах // Дискрет. анализ и исслед. операций. Сер. 1. 2005. Т. 12, №3. С. 48–53.
[6] Визинг В. Г. О (p, q)-раскраске инциденторов неориентированного мультиграфа // Дискрет. анализ и исслед. операций. Сер. 1. 2005. Т. 12, №4. С. 23–39.
[7] Визинг В. Г., Мельников Л. С., Пяткин А. В. О (k, l)-раскраске инциденторов // Дискрет. анализ и исслед. операций. Сер. 1. 2000. Т. 7, №4. С. 29–37.
[8] Визинг В. Г., Пяткин А. В. Раскраска инциденторов мультиграфа // Topics in graph theory. 2013. С. 197–209.
[9] Пяткин А. В. Hекотоpые задачи оптимизации pасписания пеpедачи сообщений в локальной сети связи // Дискрет. анализ и исслед. опеpаций. 1995. Т. 2, №4. С. 74–79.
Pyatkin A. V. Some optimization problems of scheduling the transmission of messages in a local communication network // Operations research and discrete analysis. Netherlands: Kluwer Acad. Publ., 1997. P. 227–232.
[10] Пяткин А. В. (k, l)-Раскраска инциденторов кубических мультиграфов // Дискрет. анализ и исслед. операций. Сер. 1. 2002. Т. 9, №1. С. 49–53.
[11] Пяткин А. В. Некоторые верхние оценки для инциденторного (k, l)-хроматического числа // Дискрет. анализ и исслед. операций. Сер. 1. 2003. Т. 10, №2. С. 66–78.
[12] Пяткин А. В. Верхние и нижние оценки для инциденторного (k, l)-хроматического числа // Дискрет. анализ и исслед. операций. Сер. 1. 2004. Т. 11, №1. С. 93–102.
[13] Пяткин А. В. Об (1, 1)-раскраске инциденторов мультиграфов степени 4 // Дискрет. анализ и исслед. операций. Сер. 1. 2004. Т. 11, №3.
С. 59–62.
[14] Севастьянов С. В. Об интервальной раскрашиваемости рЁебер двудольного графа // Методы дискретного анализа в решении экстремальных задач. Вып. 50. Новосибирск: ИМ СО АН СССР, 1990. C. 61–72.
[15] Asratian A. S., Kamalian R. R. Investigation of interval edge-colorings of graphs // J. Comb. Theory. Ser. B. 1964. Vol. 62, No. 1. P. 34–43.
[16] Hansen H. M. Scheduling with minimum waiting periods: Thes. ... magister sci. Odense, Denmark: Odense Univ., 1992.
[17] Hanson D., Loten C. O. M., Toft B. On interval colourings of bi-regular bipartite graphs // Ars Comb. 1998. Vol. 50. P. 23–32.
[18] Khachatrian H., Petrosyan P. Interval non-edge-colorable bipartite graphs and multigraphs // J. Graph Theory, 76, No. 3, 200–216, 2014.
[19] Lipsky W., Jr. One more polynomial complete consecutive retrieval problem // Inf. Proc. Lett. 1977. Vol. 6, No. 3. P. 91–93
