TY - JOUR
T1 - Classes of graphs without star forests and related graphs
AU - Atminas, Aistis
N1 - Publisher Copyright:
© 2022 Elsevier B.V.
PY - 2022/12
Y1 - 2022/12
N2 - This work provides a structural characterisation of hereditary graph classes that do not contain a star forest, several graphs obtained from star forests by subset complementation, a union of cliques, and the complement of a union of cliques as induced subgraphs. This provides, for instance, structural results for graph classes not containing a matching and several complements of a matching. In terms of the speed of hereditary graph classes, our results imply that all such classes have at most factorial speed of growth.
AB - This work provides a structural characterisation of hereditary graph classes that do not contain a star forest, several graphs obtained from star forests by subset complementation, a union of cliques, and the complement of a union of cliques as induced subgraphs. This provides, for instance, structural results for graph classes not containing a matching and several complements of a matching. In terms of the speed of hereditary graph classes, our results imply that all such classes have at most factorial speed of growth.
KW - Factorial speed of growth
KW - Matchings
KW - Monotone grid classes for permutations
KW - Star forests
UR - http://www.scopus.com/inward/record.url?scp=85134803293&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2022.113089
DO - 10.1016/j.disc.2022.113089
M3 - Article
AN - SCOPUS:85134803293
SN - 0012-365X
VL - 345
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 12
M1 - 113089
ER -