graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, 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 discret ...

whose

line graph In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...

is a

perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

. Equivalently, these are the graphs in which every odd-length

simple cycle In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph with ...

is a triangle. A graph is line perfect if and only if each of its

biconnected component In graph theory, a biconnected component or block (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. Th ...

s is a

bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

, 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 i ...

, 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 have the same size, and that the

chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), 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 colorin ...

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 criteria, from some set of available alternatives. It is generally divided into two subfiel ...

, mr = 509968 , pages = 236–238 , title = On line-perfect graphs , volume = 15 , year = 1978. {{Cite Geometric Algorithms and Combinatorial Optimization {{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 applicati ...

, 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