Line Perfect Graph on:
[Wikipedia]
[Google]
[Amazon]
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.
A graph is line perfect if and only if each of its biconnected components is a
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.
A graph is line perfect if and only if each of its biconnected components is a bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
, the complete graph , or a triangular book . Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect. By similar reasoning, every line perfect graph is a parity graph, a Meyniel graph, 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
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
In computer science, the problem of finding a minimum vertex cover is a classical optimizat ...
have the same size, and that the chromatic index equals the maximum degree
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
.
See also
* Strangulated graph, a graph in which everyperipheral cycle
In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygo ...
is a triangle
References
{{reflist, refs= {{citation , last = de Werra , first = D. , doi = 10.1007/BF01609025 , issue = 2 , journal = Mathematical Programming , mr = 509968 , pages = 236–238 , title = On line-perfect graphs , volume = 15 , year = 1978. {{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. {{citation , last = Maffray , first = Frédéric , doi = 10.1016/0095-8956(92)90028-V , issue = 1 , journal =Journal of Combinatorial Theory
The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...
, mr = 1159851
, pages = 1–8
, series = Series B
, title = Kernels in perfect line-graphs
, volume = 55
, year = 1992, doi-access = free
.
{{citation
, last = Trotter , first = L. E., Jr.
, doi = 10.1007/BF01593791
, issue = 2
, journal = Mathematical Programming
, mr = 0457293
, pages = 255–259
, title = Line perfect graphs
, volume = 12
, year = 1977
{{citation
, last = Wagler , first = Annegret
, contribution = Critical and anticritical edges in perfect graphs
, doi = 10.1007/3-540-45477-2_29
, mr = 1905643
, pages = 317–327
, publisher = Springer , location = Berlin
, series = Lecture Notes in Computer Science
, title = Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings
, volume = 2204
, year = 2001.
Perfect graphs