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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

[trotter-1] Б Trotter, LE, Jr. (1977), "Линейные совершенные графы", Математическое программирование , 12 (2): 255-259, DOI : 10.1007 / BF01593791 , MR 0457293

[maffray-2] Маффре, Фредерик (1992), «Ядра в совершенных линейных графах», Журнал комбинаторной теории , серия B, 55 (1): 1–8, DOI : 10.1016 / 0095-8956 (92) 90028-V , MR 1159851 .

[gls-3] Grötschel, Мартин ; Ловас, Ласло ; Шрайвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, 2 (2-е изд.), Springer-Verlag, Berlin, p. 281, DOI : 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, DOI : 10.1007 / 3-540-45477-2_29 , MR 1905643 .

[dewerra-5] Де Werra, D. (1978), "На линии идеальный графов", Математическое программирование , 15 (2): 236-238, DOI : 10.1007 / BF01609025 , MR 0509968 .

[1]