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 K4, or a triangular book K1,1,n.[2] Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect.[1] By similar reasoning, every line perfect graph is a parity graph,[3] a Meyniel graph,[4] 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 equals the maximum degree.[5]
^ abCite error: The named reference trotter was invoked but never defined (see the help page).
^Cite error: The named reference maffray was invoked but never defined (see the help page).
^Cite error: The named reference gls was invoked but never defined (see the help page).
^Cite error: The named reference wagler was invoked but never defined (see the help page).
^Cite error: The named reference dewerra was invoked but never defined (see the help page).
and 20 Related for: Line perfect graph information
In the mathematical discipline of graph theory, the linegraph of an undirected graph G is another graph L(G) that represents the adjacencies between edges...
In graph theory, a perfectgraph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every...
In graph theory, a lineperfectgraph is a graph whose linegraph is a perfectgraph. Equivalently, these are the graphs in which every odd-length simple...
In graph theory, the strong perfectgraph theorem is a forbidden graph characterization of the perfectgraphs as being exactly the graphs that have neither...
In graph theory, the perfectgraph theorem of László Lovász (1972a, 1972b) states that an undirected graph is perfect if and only if its complement graph...
results concerns perfectgraphs: every bipartite graph, the complement of every bipartite graph, the linegraph of every bipartite graph, and the complement...
Meyniel graphs are a subclass of the perfectgraphs. Every induced subgraph of a Meyniel graph is another Meyniel graph, and in every Meyniel graph the size...
Appendix:Glossary of graph theory in Wiktionary, the free dictionary. This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes...
intersection graph of the intervals. Interval graphs are chordal graphs and perfectgraphs. They can be recognized in linear time, and an optimal graph coloring...
subclasses of the perfectgraphs, block graphs are perfect. Every tree, cluster graph, or windmill graph is a block graph. Every block graph has boxicity at...
mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful...
same parity, and the lineperfectgraphs, a generalization of the bipartite graphs. Every parity graph is a Meyniel graph, a graph in which every odd cycle...
graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject...
reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel...
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to...
These graphs do not fall into many known families of well-structured graphs: they might not be perfectgraphs, circle graphs, or chordal graphs. An exception...
of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are...
mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context...
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an...
Global Information