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 04:58, 15 June 2017 (re-use illo). 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]

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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Line_perfect_graph&oldid=785739809"