Classes of graphs without star forests and related graphs

Aistis Atminas

doi:10.1016/j.disc.2022.113089

Classes of graphs without star forests and related graphs

Aistis Atminas

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

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.

Original language	English
Article number	113089
Journal	Discrete Mathematics
Volume	345
Issue number	12
DOIs	https://doi.org/10.1016/j.disc.2022.113089
Publication status	Published - Dec 2022

Keywords

Factorial speed of growth
Matchings
Monotone grid classes for permutations
Star forests

Access to Document

10.1016/j.disc.2022.113089

Cite this

@article{3e6ca5a844f04d0e82e76fb50a13b39f,

title = "Classes of graphs without star forests and related graphs",

abstract = "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.",

keywords = "Factorial speed of growth, Matchings, Monotone grid classes for permutations, Star forests",

author = "Aistis Atminas",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2022",

month = dec,

doi = "10.1016/j.disc.2022.113089",

language = "English",

volume = "345",

journal = "Discrete Mathematics",

issn = "0012-365X",

number = "12",

}

TY - JOUR

T1 - Classes of graphs without star forests and related graphs

AU - Atminas, Aistis

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 - https://www.scopus.com/pages/publications/85134803293

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 -

Classes of graphs without star forests and related graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this