Jump to content

Line perfect graph

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 05:04, 15 June 2017 (de werra). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
A line perfect graph. The edges in each biconnected component are colored black if the component is bipartite, blue if the component is a tetrahedron, and red if the component is a book of triangles.

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 , or a triangular book .[2] Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect.[1]

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.[3]

References

  1. ^ 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)
  2. ^ 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.
  3. ^ de Werra, D. (1978), "On line-perfect graphs", Mathematical Programming, 15 (2): 236–238, doi:10.1007/BF01609025, MR 0509968.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Line_perfect_graph&oldid=785740503"