Переполненный граф

Переполненный граф (англ. overfull graph) [1] — это такой простой граф (без кратных ребер и петель), размер которого больше произведения максимальной степени его вершин на округлённую вниз половину его порядка

.

Если граф имеет переполненный подграф и = то - называется графом с переполненным подграфом (англ. subgraph-overfull graph)[2][3].

Понятие переполненный граф было введено при рассмотрении задач о раскраске ребер графа, а именно при решении вопроса о принадлежности графа к Классу 1 или Классу 2. Как следует из Теоремы Визинга, хроматический индекс графа может быть либо , и тогда граф принадлежит к Классу 1, либо и тогда граф принадлежит к Классу 2.

Свойства

Некоторые свойства переполненных графов:

  • Из теоремы[1], которая гласит, что если граф обладает размером , таким что , где есть реберное число независимости, а есть максимальная степень его вершин , то граф принадлежит Классу 2, и условия, что если граф порядка , то его реберное число независимости , вытекает свойство:
Переполненный граф является графом Класса 2
  • Доказывается как теорема[2]:
Если у графа есть переполненный подграф, то сам граф - переполненный
  • Доказывается как теорема[1].
Порядок переполненного графа - нечётное число

Гипотеза о переполнении

Четуинд и Хилтон [4] в 1986 г. выдвинули гипотезу, известную сейчас как гипотеза о переполнении (англ. Overfull Graph Conjecture)

Если для максимальной степени вершин графа выполняется условие , где есть порядок графа, то граф принадлежит к Классу 2 тогда и только тогда, когда он является графом с переполненным подграфом.

Эта гипотеза, если верна, имела бы многочисленные приложения к теории графов, включая гипотезу об 1-факторизации [5].

Алгоритмы

В работе [6] приводится алгоритм, которые позволяет найти для графа у которого все порожденные переполненные подграфы за время , где и .

Вариант этого алгоритма позволяет для графа , у которго найти все порожденные переполненные подграфы за линейное время .

Также в работе приводится второй алгоритм, работающий с использованием первого алгоритма, который позволяет найти все порожденные переполненные подграфы графа , у которго в общем случае за полиномиальное время , а для регулярного графа за время .

Примечания

Литература

Chartran G., Zhang P. Chromatic Graph Theory (англ.) / Series Editor Kenneth H. Rosen. — Baca Ration, London, New York: Chapman & Hall/CRC, 2009. — P. 483. — (Discrete Mathematics and Its Applications). — ISBN 978-1-58488-800-0.


  • Chetwynd A. G., Hilton A. J. W. Star multigraphs with three vertices of maximum degree (англ.) // Mathematical Proceedings of the Cambridge Philosophical Society. — 1986. Vol. 100, iss. 2. P. 303–317. doi:10.1017/S030500410006610X.
  • Chetwynd A. G., Hilton A. J. W. 1-factorizing regular graphs of high degree—an improved bound (англ.) // Mathematics. — 1989. Vol. 75, iss. 1–3. P. 103–112. doi:10.1016/0012-365X(89)90082-4.
  • Hilton A. J. W. Two conjectures on edge-colouring (англ.) // Discrete Mathematics. — 1989. Vol. 74. P. 61-64.
  • Niessen T. How to find overfull subgraphs in graphs with large maximum degree. II (англ.) // Electronic Journal of Combinatorics. — 2001. Vol. 8, iss. 1. (Research Paper 7)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.