All basic graphs are perfect
ProvedStrongPerfectGraph.Main.basic_perfectgraph-theoryperfect-graphs
Let be a finite simple graph. Following the paper, is basic if one of the following holds:
- is bipartite;
- is bipartite;
- is isomorphic to the line graph of a bipartite graph ;
- is isomorphic to the line graph of a bipartite graph;
- is a double split graph.
Then every basic graph is perfect:
The paper states "It is easy to see that all basic graphs are perfect": for bipartite graphs this is trivial; for line graphs of bipartite graphs it is König's edge-colouring theorem; for their complements it follows from Lovász's theorem 1.1; and for double split graphs it is left to the reader. It is one of the ingredients of the derivation of Theorem 1.2 from the decomposition theorem 1.3.
Formalization Note IsBasic is the mission definition; line graphs are taken of a graph on Fin n, up to graph isomorphism.
Preamble
import Mathlib import Definitions.Def_StrongPerfectGraph_Main_IsBasic import Definitions.Def_StrongPerfectGraph_Main_IsPerfect
Formal statement
namespace StrongPerfectGraph.Main
/-- Every basic graph is perfect (p. 53). -/
theorem basic_perfect {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (hG : IsBasic G) : 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 (sentence "It is easy to see that all basic graphs are perfect", after the definition of basic graphs)