graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a line perfect graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

whose

line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

is a

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfe ...

. 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 component In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks a ...

s is a bipartite graph, the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

, 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 In graph theory, a parity graph is a graph in which every two induced paths between the same two vertices have the same parity: either both paths have odd length, or both have even length.

, a

Meyniel graph In graph theory, a Meyniel graph is a graph in which every odd cycle of length five or more has at least two chords (edges connecting non-consecutive vertices of the cycle). The chords may be uncrossed (as shown in the figure) or they may cross ...

, and a

perfectly orderable graph In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a s ...

. Line perfect graphs generalize the bipartite graphs, and share with them the properties that the

maximum matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adj ...

and minimum vertex cover have the same size, and that the

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blu ...

equals the maximum degree.

References

{{reflist, refs= {{citation , last = de Werra , first = D. , doi = 10.1007/BF01609025 , issue = 2 , journal =

Mathematical Programming Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

, 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 , 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 =

, 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

See also

References