p. 3:27 — α(H)ω(H) ≥ |V(H)| for intersection graphs of subtrees of a tree
ProvedTwinWidthI.MinorFree.indep_mul_clique_gechordal-graphgraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1perfect-graph
Suppose a finite graph is the intersection graph of subtrees of a tree: each vertex has a connected subtree , and distinct vertices are adjacent exactly when their subtrees intersect. Then
where is the largest size of an independent set and the largest size of a clique. The paper applies this to the intersection graph of enhanced DFS subtrees.
Preamble
import Mathlib import Definitions.Def_GavrilSubtree_Chordal_Setting import Definitions.Def_TwinWidthI_MinorFree_Setting
Formal statement
namespace TwinWidthI.MinorFree
/-- The numerical consequence of perfection for a finite subtree intersection graph (p. 3:27). -/
theorem indep_mul_clique_ge {W β : Type} [Fintype W]
(H : SimpleGraph W) (T : SimpleGraph β) (F : W → Set β)
(hF : GavrilSubtree.Chordal.IsSubtreeRep H T F) :
Fintype.card W ≤ H.indepNum * H.cliqueNum := 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:27, proof of Theorem 6.3, paragraph 'The intersection graph H of the enhancements'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.