Independence number and odd dominating models
In the authors' words
A dominating -model, introduced by Illingworth and Wood [J. Graph Theory, 2025], is a sequence of pairwise vertex-disjoint subtrees of such that every vertex of has a neighbour in for . Let denote the maximum order of such a model. We prove two dominating-model analogues of improvements to the classical Duchet-Meyniel bound [Ann. Discrete Math., 1982]. The first extends a result of Kawarabayashi, Plummer, and Toft [J. Combin. Theory Ser. B, 2005]. Every -vertex graph with satisfies . Second, we prove a constant-factor improvement of the Duchet-Meyniel bound for dominating models: every graph satisfies . This qualitatively extends the results of Fox [SIAM J. Discrete Math., 2010] and Balogh and Kostochka [Discrete Math., 2011]. An odd dominating -model is a dominating -model with an assignment of one of two colours to each vertex of , such that every edge of each is bichromatic and, for , some edge between and is monochromatic. Let denote the maximum order of such a model. Our constant-factor improvement of the Duchet-Meyniel bound relies on our next result: every claw-free graph satisfies , generalising a result of Chudnovsky and Fradkin [J. Graph Theory, 2010]. The factor 2/3 is asymptotically best possible. For , we prove that every -vertex graph with no odd dominating -model has independence number at least . For the stronger notion in which every vertex of has a neighbour of the same colour in , we prove the analogous results with replaced by .
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: v1