Double split graphs are perfect
ProvedStrongPerfectGraph.Main.double_split_perfectgraph-theoryperfect-graphs
Let and let be a double split graph: is partitioned into , , , , where
- is adjacent to for every , and is nonadjacent to for every ;
- there are no edges between and for , and all four edges between and for ;
- for every there are exactly two edges between and , and these two edges have no common end.
Then is perfect:
The paper says "for double split graphs we leave it to the reader" when asserting that all basic graphs are perfect (p. 53). It is the double-split case of that assertion.
Formalization Note IsDoubleSplit is the mission definition: an equivalence labels as inl (i,false), inl (i,true) and as inr (j,false), inr (j,true).
Preamble
import Mathlib import Definitions.Def_StrongPerfectGraph_Main_IsBasic import Definitions.Def_StrongPerfectGraph_Main_IsPerfect
Formal statement
namespace StrongPerfectGraph.Main
/-- Double split graphs are perfect (p. 53, "left to the reader"). -/
theorem double_split_perfect {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (hG : IsDoubleSplit 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. 52 (definition of double split graph) and p. 53 ("for double split graphs we leave it to the reader")