Boundedness and Separation Between Induced and Non-Induced Covering Numbers
Abstract
There are four covering numbers cgπ’(H),cuπ’(H),clπ’(H),cfπ’(H), each of which measures in a slightly different way how well the edges of a graph H (called a host) can be covered with graphs of a class π’ (called a guest class). If we require the graphs of π’ to correspond to induced subgraphs of H, we obtain an induced variant icxπ’ for each covering number cxπ’ which satisfies cxπ’(H) β€ icxπ’(H) for every graph H. Yet, in general icxπ’ cannot be bounded in terms of cxπ’. If there exists for a guest class π’ and a host class β a function f such that icxπ’(H) β€ f(cxπ’(H)) for every graph H β β, we call f a binding function. Within this work, we study for which structural properties of a guest class π’ and a host class β such binding functions exist. We consider guest classes π’ that are monotone, hereditary, component-closed or neither, and have bounded maximum average degree, bounded chromatic number or neither. The host classes β we consider have bounded treewidth, exclude some minor, have bounded maximum average degree, bounded chromatic number, or none of these properties. For $219$ out of the $240$ possible $3$-tuples of properties for π’ and β and covering numbers we either provide a binding function or an example where no such function exists. In particular, we show that such binding functions always exist for hereditary guest classes π’ of bounded maximum average degree for three of the four covering numbers, but may not for the fourth kind.
Related
BibTeX
@misc{goetze2026boundedness,
title = {{Boundedness and Separation Between Induced and Non-Induced Covering Numbers}},
author = {Miriam Goetze and Yidi Zang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09873},
eprint = {2609.09873},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09873},
}
RIS
TY - UNPB
TI - Boundedness and Separation Between Induced and Non-Induced Covering Numbers
AU - Miriam Goetze
AU - Yidi Zang
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.09873
UR - https://arxiv.org/abs/2609.09873
AB - There are four covering numbers c_g^π’(H),c_u^π’(H),c_l^π’(H),c_f^π’(H), each of which measures in a slightly different way how well the edges of a graph H (called a host) can be covered with graphs of a class π’ (called a guest class). If we require the graphs of π’ to correspond to induced subgraphs of H, we obtain an induced variant ic_x^π’ for each covering number c_x^π’ which satisfies c_x^π’(H) β€ ic_x^π’(H) for every graph H. Yet, in general ic_x^π’ cannot be bounded in terms of c_x^π’. If there exists for a guest class π’ and a host class β a function f such that ic_x^π’(H) β€ f(c_x^π’(H)) for every graph H β β, we call f a binding function. Within this work, we study for which structural properties of a guest class π’ and a host class β such binding functions exist. We consider guest classes π’ that are monotone, hereditary, component-closed or neither, and have bounded maximum average degree, bounded chromatic number or neither. The host classes β we consider have bounded treewidth, exclude some minor, have bounded maximum average degree, bounded chromatic number, or none of these properties. For $219$ out of the $240$ possible $3$-tuples of properties for π’ and β and covering numbers we either provide a binding function or an example where no such function exists. In particular, we show that such binding functions always exist for hereditary guest classes π’ of bounded maximum average degree for three of the four covering numbers, but may not for the fourth kind.
ER -