WikiDer > Линейный идеальный график

Line perfect graph
Линейный идеальный график. Ребра в каждом двусвязном компоненте окрашены в черный цвет, если компонент является двудольным, синий, если компонент представляет собой тетраэдр, и красный, если компонент представляет собой книгу треугольников.

В теория графов, а линейный идеальный график это граф, линейный график это идеальный график. Эквивалентно, это графы, в которых каждая нечетная длина простой цикл представляет собой треугольник.[1]

График является линейным тогда и только тогда, когда каждый из его двусвязные компоненты это двудольный граф, то полный график , или треугольная книга .[2] Поскольку все эти три типа двусвязных компонентов являются совершенными графами, каждый линейный идеальный граф сам совершенен.[1] По аналогичным соображениям каждый линейный идеальный граф является граф четности,[3] а График Мейниеля,[4] и идеально упорядочиваемый график.

Линейные совершенные графы обобщают двудольные графы и разделяют с ними свойства, присущие максимальное соответствие и минимальное покрытие вершины имеют одинаковый размер, и что хроматический индекс равно максимальная степень.[5]

Смотрите также

Рекомендации

  1. ^ а б Троттер, Л. Э. младший (1977), "Линейные совершенные графы", Математическое программирование, 12 (2): 255–259, Дои:10.1007 / BF01593791, МИСТЕР 0457293
  2. ^ Маффре, Фредерик (1992), "Ядра в совершенных линейных графах", Журнал комбинаторной теории, Серия B, 55 (1): 1–8, Дои:10.1016 / 0095-8956 (92) 90028-В, МИСТЕР 1159851.
  3. ^ Грётшель, Мартин; Ловас, Ласло; Шрайвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, 2 (2-е изд.), Springer-Verlag, Berlin, p. 281, Дои:10.1007/978-3-642-78240-4, ISBN 3-540-56740-2, МИСТЕР 1261419.
  4. ^ Ваглер, Аннегрет (2001), "Критические и антикритические ребра в совершенных графах", Теоретико-графические концепции в компьютерных науках: 27-й международный семинар, WG 2001, Больтенхаген, Германия, 14–16 июня 2001 г., Труды, Конспект лекций по информатике, 2204, Берлин: Springer, стр. 317–327, Дои:10.1007/3-540-45477-2_29, МИСТЕР 1905643.
  5. ^ де Верра, Д. (1978), "Линейно-совершенные графы", Математическое программирование, 15 (2): 236–238, Дои:10.1007 / BF01609025, МИСТЕР 0509968.