On the Typical Structure of Graphs in a Monotone Property
2014 (English)In: The Electronic Journal of Combinatorics, ISSN 1077-8926, Vol. 21, no 3, P3.34- p.Article in journal (Refereed) Published
Given a graph property P, it is interesting to determine the typical structure of graphs that satisfy P. In this paper, we consider monotone properties, that is, properties that are closed under taking subgraphs. Using results from the theory of graph limits, we show that if P is a monotone property and r is the largest integer for which every r-colorable graph satisfies P, then almost every graph with P is close to being a balanced r-partite graph.
Place, publisher, year, edition, pages
2014. Vol. 21, no 3, P3.34- p.
Graph limits, Monotone properties, Structure of graphs
IdentifiersURN: urn:nbn:se:uu:diva-233011ISI: 000341119300002OAI: oai:DiVA.org:uu-233011DiVA: diva2:754179