Proof of Corollary 5, p. 6 — domination composes to 2-domination
ProvedP7ThreeColor.Seed.dominating_of_dominatingdominating-setgraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite simple graph, a dominating vertex set, and a connected vertex set. Suppose every vertex of lies in or has a neighbor in . Then is connected and 2-dominates :
This is the domination step used when Corollary 5 finds a small connected dominating set inside the graph induced by .
Formalization Note The theorem states the domination implication for any cardinality of ; in the paper it is applied when . The hypothesis about vertices of is precisely domination of by .
Preamble
import Mathlib import Definitions.Def_P7ThreeColor_Seed_Basic
Formal statement
namespace P7ThreeColor.Seed
/-- Proof of Corollary 5, p. 6: a connected set dominating a dominating set is 2-dominating. -/
theorem dominating_of_dominating {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (S T : Finset V)
(hS : IsDominating G S) (hTS : T ⊆ S)
(hTdom : ∀ v ∈ S, v ∈ T ∨ ∃ t ∈ T, G.Adj v t)
(hTconn : (G.induce (T : Set V)).Connected) :
(G.induce (T : Set V)).Connected ∧ IsTwoDominating G T := by sorry
end P7ThreeColor.Seed
Source
Bonomo, Chudnovsky, Maceli, Schaudt, Stein and Zhong, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, Combinatorica (2017), DOI 10.1007/s00493-017-3553-8, p. 6, proof of Corollary 5, sentence beginning 'If |S′| ≤ 3'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.