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

DOI10.1016/J.JCTB.2018.02.002zbMATH Open1387.05168arXiv1507.04944OpenAlexW2962880231WikidataQ130150537 ScholiaQ130150537MaRDI QIDQ1748271FDOQ1748271

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)

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.

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

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

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)

Cites Work

• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hypergraph containers
• Independent sets in hypergraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Range of values of the entropy of hereditary classes of graphs
• Title not available (Why is that?)
• Excluding induced subgraphs: quadrilaterals
• Excluding Induced Subgraphs III: A General Asymptotic
• Excluding induced subgraphs. II: Extremal graphs
• The structure of almost all graphs in a hereditary property
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Excluding induced subgraphs: critical graphs
• Almost all Berge Graphs are Perfect
• Hereditary and monotone properties of combinatorial structure
• 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

Cited In (4)

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

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)