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

DOI10.1016/J.JCTB.2018.02.002MaRDI QIDQ1748271zbMATHOpenAlexWikidataFDO

Authors Daniela Kühn, Deryk Osthus, Timothy Townsend, Jaehoon 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

induced subgraphsrandom graphstypical 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)

Abstract: We determine, for all $kgeq6$, the typical structure of graphs that do not contain an induced $2k$-cycle. This verifies a conjecture of Balogh and Butterfield. Surprisingly, the typical structure of such graphs is richer than that encountered in related results. The approach we take also yields an approximate result on the typical structure of graphs without an induced $8$-cycle or without an induced $10$-cycle.

Recommendations

• Even cycles in graphs with many odd cycles
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• Degree powers in graphs with a forbidden even cycle
• Forbidden pairs and the existence of a dominating cycle
• The Even Cycle Problem for Directed Graphs
• Forbidden subgraphs and the existence of paths and cycles passing through specified vertices
• Even cycles in graphs
• Even cycles in directed graphs
• Even Cycles in Directed Graphs
• The strong clique index of a graph with forbidden cycles

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 3134390 (Why is no real title available?)
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• scientific article; zbMATH DE number 3258858 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 970795 (Why is no real title available?)
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Almost all Berge Graphs are Perfect
• Excluding Induced Subgraphs III: A General Asymptotic
• Excluding induced subgraphs. II: Extremal graphs
• Excluding induced subgraphs: critical graphs
• Excluding induced subgraphs: quadrilaterals
• For which densities are random triangle-free graphs almost surely bipartite?
• Hereditary and monotone properties of combinatorial structure
• Hypergraph containers
• Independent sets in hypergraphs
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Range of values of the entropy of hereditary classes of graphs
• The structure of almost all graphs in a hereditary property
• The typical structure of sparse \(K_{r+1}\)-free graphs

Cited in

(4)

• An asymmetric container lemma and the structure of graphs with no induced $4$-cycle
• Structure and enumeration theorems for hereditary properties in finite relational languages
• Almost all string graphs are intersection graphs of plane convex sets
• The regularity of almost all edge ideals

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1748271)