Editing Perfect graph (section)

===Bipartite graphs and line graphs===
[[File:Bipartite line graph.svg|thumb|upright=1.35|A bipartite graph (left) and its line graph (right). The shaded cliques in the line graph correspond to the vertices of the underlying bipartite graph, and have size equal to the degree of the corresponding vertex.]]
In [[bipartite graph]]s (with at least one edge) the chromatic number and clique number both equal two. Their induced subgraphs remain bipartite, so bipartite graphs are perfect.{{r|hougardy-2006}} Other important families of graphs are bipartite, and therefore also perfect, including for instance the [[Tree (graph theory)|trees]] and [[median graph]]s.{{r|bipartite}} By the perfect graph theorem, maximum independent sets in bipartite graphs have the same size as their minimum clique covers. The maximum independent set is complementary to a minimum [[vertex cover]], a set of vertices that touches all edges. A minimum clique cover consists of a [[maximum matching]] (as many disjoint edges as possible) together with one-vertex cliques for all remaining vertices, and its size is the number of vertices minus the number of matching edges. Therefore, this equality can be expressed equivalently as an equality between the size of the maximum matching and the minimum vertex cover in bipartite graphs, the usual formulation of [[Kőnig's theorem (graph theory)|Kőnig's theorem]].{{r|konig-1931|trotter-1977}}

A matching, in any graph <math>G</math>, is the same thing as an independent set in the [[line graph]] <math>L(G)</math>, a graph that has a vertex for each edge in <math>G</math> and an edge between two vertices in <math>L(G)</math> for each pair of edges in <math>G</math> that share an endpoint. Line graphs have two kinds of cliques: sets of edges in <math>G</math> with a common endpoint, and triangles in <math>G</math>. In bipartite graphs, there are no triangles, so a clique cover in <math>L(G)</math> corresponds to a vertex cover in <math>G</math>. Therefore, in line graphs of bipartite graphs, the independence number and clique cover number are equal. Induced subgraphs of line graphs of bipartite graphs are line graphs of subgraphs, so the line graphs of bipartite graphs are perfect.{{r|trotter-1977}} Examples include the [[rook's graph]]s, the line graphs of [[complete bipartite graph]]s. Every line graph of a bipartite graph is an induced subgraph of a rook's graph.{{r|bg-2006}}

Because line graphs of bipartite graphs are perfect, their clique number equals their chromatic number. The clique number of the line graph of a bipartite graph is the [[degree (graph theory)|maximum degree]] of any vertex of the underlying bipartite graph. The chromatic number of the line graph of a bipartite graph is the [[chromatic index]] of the underlying bipartite graph, the minimum number of colors needed to color the edges so that touching edges have different colors. Each color class forms a matching, and the chromatic index is the minimum number of matchings needed to cover all edges. The equality of maximum degree and chromatic index, in bipartite graphs, is another theorem of [[Dénes Kőnig]].{{r|konig-1916}} In arbitrary simple graphs, they can differ by one; this is [[Vizing's theorem]].{{r|trotter-1977}}

[[File:Line perfect graph.svg|thumb|A [[line perfect graph]], with black bipartite biconnected components, blue <math>K_4</math>, and red triangular books]]
The underlying graph <math>G</math> of a perfect line graph <math>L(G)</math> is a [[line perfect graph]]. These are the graphs whose [[biconnected component]]s are  bipartite graphs, the [[complete graph]] <math>K_4</math>, and [[Book (graph theory)|triangular books]], sets of triangles sharing an edge. These components are perfect, and their combination preserves perfection, so every line perfect graph is perfect.{{r|trotter-1977}}

The bipartite graphs, their complements, and the line graphs of bipartite graphs and their complements form four basic classes of perfect graphs that play a key role in the proof of the strong perfect graph theorem. According to the structural decomposition of perfect graphs used as part of this proof, every perfect graph that is not already in one of these four classes can be decomposed by partitioning its vertices into subsets, in one of four ways, called a 2-join, the complement of a 2-join, a homogeneous pair, or a [[skew partition]].{{r|cornuejols-2002}}