pith. sign in

arxiv: 1507.04944 · v1 · pith:DKTTET2Pnew · submitted 2015-07-17 · 🧮 math.CO

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

classification 🧮 math.CO
keywords inducedstructuretypicalcyclegraphswithoutapproachapproximate
0
0 comments X
read the original abstract

We determine, for all $k\geq 6$, 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.