Stability of hereditary graph classes under closure operations

Title: Stability of hereditary graph classes under closure operations
Creator: Miller, Mirka; Ryan, Joe; Ryjáček, Zdeněk; Teska, Jakub; Vrána, Petr
Relation: Journal of Graph Theory Vol. 74, Issue 1, p. 67-80
Publisher Link: http://dx.doi.org/10.1002/jgt.21692
Publisher: John Wiley & Sons, Inc.
Resource Type: journal article
Date: 2013
Description: If C is a subclass of the class of claw-free graphs, then C is said to be stable if, for any GaC, the local completion of G at any vertex is also in C. If cl is a closure operation that turns a claw-free graph into a line graph by a series of local completions and C is stable, then cl(G)aC for any GaC. In this article, we study stability of hereditary classes of claw-free graphs defined in terms of a family of connected closed forbidden subgraphs. We characterize line graph preimages of graphs in families that yield stable classes, we identify minimal families that yield stable classes in the finite case, and we also give a general background for techniques for handling unstable classes by proving that their closure may be included into another (possibly stable) class.
Subject: closure; stable class; forbidden subgraph
Identifier: http://hdl.handle.net/1959.13/1057749
Identifier: uon:16253
Identifier: ISSN:0364-9024
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format