Line perfect graph: Difference between revisions
short description Tags: Mobile edit Mobile app edit iOS app edit |
Erel Segal (talk | contribs) Use citation template |
||
| Line 25: | Line 25: | ||
| year = 1978}}.</ref> |
| year = 1978}}.</ref> |
||
<ref name=gls>{{Cite Geometric Algorithms and Combinatorial Optimization}}</ref> |
|||
<ref name=gls>{{citation |
|||
| last1 = Grötschel | first1 = Martin | author1-link = Martin Grötschel |
|||
| last2 = Lovász | first2 = László | author2-link = László Lovász |
|||
| last3 = Schrijver | first3 = Alexander | author3-link = Alexander Schrijver |
|||
| doi = 10.1007/978-3-642-78240-4 |
|||
| edition = 2nd |
|||
| isbn = 3-540-56740-2 |
|||
| mr = 1261419 |
|||
| page = 281 |
|||
| publisher = Springer-Verlag, Berlin |
|||
| series = Algorithms and Combinatorics |
|||
| title = Geometric algorithms and combinatorial optimization |
|||
| url = https://books.google.com/books?id=hWvmCAAAQBAJ&pg=PA281 |
|||
| volume = 2 |
|||
| year = 1993}}.</ref> |
|||
<ref name=maffray>{{citation |
<ref name=maffray>{{citation |
||
Revision as of 11:07, 28 January 2024
In graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle.[1]
A graph is line perfect if and only if each of its biconnected components is a bipartite graph, the complete graph K4, or a triangular book K1,1,n.[2] Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect.[1] By similar reasoning, every line perfect graph is a parity graph,[3] a Meyniel graph,[4] and a perfectly orderable graph.
Line perfect graphs generalize the bipartite graphs, and share with them the properties that the maximum matching and minimum vertex cover have the same size, and that the chromatic index equals the maximum degree.[5]
See also
- Strangulated graph, a graph in which every peripheral cycle is a triangle
References
- ^ a b Trotter, L. E., Jr. (1977), "Line perfect graphs", Mathematical Programming, 12 (2): 255–259, doi:10.1007/BF01593791, MR 0457293
{{citation}}: CS1 maint: multiple names: authors list (link) - ^ Maffray, Frédéric (1992), "Kernels in perfect line-graphs", Journal of Combinatorial Theory, Series B, 55 (1): 1–8, doi:10.1016/0095-8956(92)90028-V, MR 1159851.
- ^ Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419
- ^ Wagler, Annegret (2001), "Critical and anticritical edges in perfect graphs", Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings, Lecture Notes in Computer Science, vol. 2204, Berlin: Springer, pp. 317–327, doi:10.1007/3-540-45477-2_29, MR 1905643.
- ^ de Werra, D. (1978), "On line-perfect graphs", Mathematical Programming, 15 (2): 236–238, doi:10.1007/BF01609025, MR 0509968.