Линейный идеальный график - Line perfect graph

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

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

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

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

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

Удушенный граф, граф, в котором каждый периферический цикл это треугольник

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

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

[trotter-1] а ^б Троттер, Л. Э. младший (1977), "Линейные совершенные графы", Математическое программирование, 12 (2): 255–259, Дои:10.1007 / BF01593791, МИСТЕР 0457293

[maffray-2] Маффре, Фредерик (1992), "Ядра в совершенных линейных графах", Журнал комбинаторной теории, Серия B, 55 (1): 1–8, Дои:10.1016 / 0095-8956 (92) 90028-В, МИСТЕР 1159851.

[gls-3] Грётшель, Мартин; Ловас, Ласло; Шрайвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, 2 (2-е изд.), Springer-Verlag, Berlin, p. 281, Дои:10.1007/978-3-642-78240-4, ISBN 3-540-56740-2, МИСТЕР 1261419.

[wagler-4] Ваглер, Аннегрет (2001), "Критические и антикритические ребра в совершенных графах", Теоретико-графические концепции в компьютерных науках: 27-й международный семинар, WG 2001, Больтенхаген, Германия, 14–16 июня 2001 г., Труды, Конспект лекций по информатике, 2204, Берлин: Springer, стр. 317–327, Дои:10.1007/3-540-45477-2_29, МИСТЕР 1905643.

[dewerra-5] де Верра, Д. (1978), "Линейно-совершенные графы", Математическое программирование, 15 (2): 236–238, Дои:10.1007 / BF01609025, МИСТЕР 0509968.

[1]

[2]

[3]

[4]

[5]