Forbidding induced even cycles in a graph: typical structure and counting

DOI10.1016/j.jctb.2018.02.002zbMath1387.05168arXiv1507.04944OpenAlexW2962880231WikidataQ130150537 ScholiaQ130150537MaRDI QIDQ1748271

Daniela Kühn, Deryk Osthus, Timothy Townsend, Jae-Hoon Kim

Publication date: 9 May 2018

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.04944

zbMATH Keywords

random graphsinduced subgraphstypical structure

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Almost all string graphs are intersection graphs of plane convex sets ⋮ The regularity of almost all edge ideals ⋮ Structure and enumeration theorems for hereditary properties in finite relational languages

Cites Work

• Hypergraph containers
• The structure of almost all graphs in a hereditary property
• Excluding induced subgraphs. II: Extremal graphs
• For which densities are random triangle-free graphs almost surely bipartite?
• The typical structure of sparse $K_{r+1}$-free graphs
• For most graphs H , most H -free graphs have a linear homogeneous set
• Excluding induced subgraphs: Critical graphs
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Excluding induced subgraphs: quadrilaterals
• Excluding Induced Subgraphs III: A General Asymptotic
• Almost all Berge Graphs are Perfect
• Independent sets in hypergraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Forbidding induced even cycles in a graph: typical structure and counting