Line graphs of bipartite graphs are perfect (König)
ProvedStrongPerfectGraph.Main.line_graph_bipartite_perfectgraph-theoryperfect-graphs
Let be a finite bipartite graph and let be its line graph: the vertices of are the edges of , two of them adjacent when they share an end. If a finite graph is isomorphic to , then is perfect:
This is König's theorem as cited on p. 53 of the paper: an induced subgraph of is the line graph of a subgraph of , which is again bipartite, and for a bipartite graph the edge-chromatic number equals the maximum degree, which is the clique number of the line graph. It is the line-graph case of "all basic graphs are perfect".
Formalization Note is a graph on Fin n, and is given together with an isomorphism G ≃g H.lineGraph, matching the line-graph clauses of the mission definition IsBasic.
Preamble
import Mathlib import Definitions.Def_StrongPerfectGraph_Main_IsPerfect
Formal statement
namespace StrongPerfectGraph.Main
/-- König: the line graph of a bipartite graph is perfect (p. 53, citing [15]). -/
theorem line_graph_bipartite_perfect {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) {n : ℕ} (H : SimpleGraph (Fin n)) (hH : H.IsBipartite)
(e : G ≃g H.lineGraph) : IsPerfect G := by sorry
end StrongPerfectGraph.Main
Source
Chudnovsky, Robertson, Seymour & Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), 51-229, p. 53 ("for line graphs of bipartite graphs it is a theorem of König [15]"), citing D. König, Math. Ann. 77 (1916), 453-465