p. 3:26 — twin-width is the maximum over connected components
ProvedTwinWidthI.MinorFree.twinWidth_componentsconnected-componentsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1twin-width
Let be a finite graph and a nonnegative integer. Then has twin-width at most exactly when every connected component of , with its induced graph, has twin-width at most :
This permits the excluded-minor argument to work component by component. The empty graph is included; its contraction sequence ends at the empty partition.
Preamble
import Mathlib import Definitions.Def_TwinWidthI_MinorFree_Setting
Formal statement
namespace TwinWidthI.MinorFree
/-- The twin-width of a graph is the maximum of that of its connected components (p. 3:26). -/
theorem twinWidth_components {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (d : ℕ) :
TwinWidthI.BoolWidth.TwinWidthLE G d ↔
∀ c : G.ConnectedComponent,
letI : Fintype c.supp := Fintype.ofFinite c.supp
letI : DecidableEq c.supp := Classical.decEq c.supp
TwinWidthI.BoolWidth.TwinWidthLE (G.induce c.supp) d := by sorry
end TwinWidthI.MinorFree
Source
Bonnet, Kim, Thomassé and Watrigant, Twin-width I: Tractable FO Model Checking, J. ACM 69(1), Article 3 (2021), p. 3:26, proof of Theorem 6.3, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.