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

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

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

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

См. также

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

Ссылки

^ Перейти обратно: ^а ^б Троттер, Л.Е. младший (1977), «Линейные совершенные графики», Mathematical Programming , 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 .
^ Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419
^ Ваглер, Аннегрет (2001), «Критические и антикритические ребра в идеальных графах», Теоретико-графовые концепции в информатике: 27-й международный семинар, WG 2001, Больтенхаген, Германия, 14–16 июня 2001 г., Труды , Конспекты лекций по информатике , том. 2204, Берлин: Springer, стр. 317–327, номер документа : 10.1007/3-540-45477-2_29 , MR 1905643 .
^ де Верра, Д. (1978), «О линейно-совершенных графах», Mathematical Programming , 15 (2): 236–238, doi : 10.1007/BF01609025 , MR 0509968 .

[trotter-1] Перейти обратно: ^а ^б Троттер, Л.Е. младший (1977), «Линейные совершенные графики», Mathematical Programming , 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] Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419

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

[dewerra-5] де Верра, Д. (1978), «О линейно-совершенных графах», Mathematical Programming , 15 (2): 236–238, doi : 10.1007/BF01609025 , MR 0509968 .

[1]

[2]

[3]

[4]

[5]