On subgraphs of C₂k-free graphs and a problem of Kühn and Osthus

DOI10.1017/S0963548319000452MaRDI QIDQ4993100zbMATH OpenFDO

Authors Dániel Grósz, Abhishek Methuku, Casey Tompkins

Publication date 15 June 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

bipartite subgraphscyclesextremal problems

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Abstract: Let $c$ denote the largest constant such that every $C_6$-free graph $G$ contains a bipartite and $C_4$-free subgraph having $c$ fraction of edges of $G$. GyH{o}ri et al. showed that $frac38leclefrac25$. We prove that $c=frac38$. More generally, we show that for any $varepsilon>0$, and any integer $kge2$, there is a $C_{2k}$-free graph $G_1$ which does not contain a bipartite subgraph of girth greater than $2k$ with more than $left(1-frac12^{2k-2}ight)frac22k-1(1+varepsilon)$ fraction of the edges of $G_1$. There also exists a $C_{2k}$-free graph $G_2$ which does not contain a bipartite and $C_4$-free subgraph with more than $left(1-frac12^{k-1}ight)frac1k-1(1+varepsilon)$ fraction of the edges of $G_2$. One of our proofs uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of ErdH{o}s: For any $varepsilon>0$, and any integers $a$, $b$, $kge2$, there exists an $a$-uniform hypergraph $H$ of girth greater than $k$ which does not contain any $b$-colorable subhypergraph with more than $left(1-frac1b^{a-1}ight)left(1+varepsilonight)$ fraction of the hyperedges of $H$. We also prove further generalizations of this theorem. In addition, we give a new and very short proof of a result of K"uhn and Osthus, which states that every bipartite $C_{2k}$-free graph $G$ contains a $C_4$-free subgraph with at least $1/(k-1)$ fraction of the edges of $G$. We also answer a question of K"uhn and Osthus about $C_{2k}$-free graphs obtained by pasting together $C_{2l}$'s (with $k>lge3$).

Recommendations

• On subgraphs of \(C_{2k}\)-free graphs
• Making a \(C_6\)-free graph \(C_4\)-free and bipartite
• The number of \(C_{2\ell}\)-free graphs
• Maximum bipartite subgraphs in graphs without short cycles
• A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs

Cites work

• \(C_ 6\)-free bipartite graphs and product representation of squares
• A Dual of Dilworth's Decomposition Theorem
• Compactness results in extremal graph theory
• Four-cycles in graphs without a given even cycle
• Making a \(C_6\)-free graph \(C_4\)-free and bipartite
• On a Probabilistic Graph-Theoretical Method
• On chromatic number of finite set-systems
• On chromatic number of graphs and set-systems
• On the Turán number for the hexagon

Cited in

(4)

• On subgraphs of \(C_{2k}\)-free graphs
• Making a \(C_6\)-free graph \(C_4\)-free and bipartite
• On the extremal number of subdivisions
• A stability theorem for maximal C2k+1 ${C}_{2k+1}$‐free graphs

This page was built for publication: On subgraphs of \(C_{2k}\)-free graphs and a problem of Kühn and Osthus

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