- Abhishek, Methuku
- 이산수학 그룹

On subgraphs of C2k-free graphs and a problem of Kühn and Osthus

- Title
- On subgraphs of C2k-free graphs and a problem of Kühn and Osthus

- Author(s)
- Dániel Grósz; Abhishek Methuku; Casey Tompkins

- Publication Date
- 2020-05

- Journal
- COMBINATORICS PROBABILITY & COMPUTING, v.29, no.3, pp.436 - 454

- Publisher
- CAMBRIDGE UNIV PRESS

- Abstract
- © Cambridge University Press 2020. Let c denote the largest constant such that every C6-free graph G contains a bipartite and C4-free subgraph having a fraction c of edges of G. Gy 'ri, Kensell and Tompkins showed that 3/8 (c)1/2 c (c)1/2 2/5. We prove that c = 38. More generally, we show that for any ϵ > 0, and any integer k (c)3/4 2, there is a C2k-free graph which does not contain a bipartite subgraph of girth greater than 2k with more than a fraction of the edges of . There also exists a C2k-free graph which does not contain a bipartite and C4-free subgraph with more than a fraction of the edges of .One of our proofs uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erd 's. For any ϵ > 0, and any integers a, b, k (c)3/4 2, there exists an a-uniform hypergraph H of girth greater than k which does not contain any b-colourable subhypergraph with more than a 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ühn and Osthus, which states that every bipartite C2k-free graph G contains a C4-free subgraph with at least a fraction 1/(k-1) of the edges of G. We also answer a question of Kühn and Osthus about C2k-free graphs obtained by pasting together C2l's (with k >l (c)3/4 3)

- ISSN
- 0963-5483

- Appears in Collections:
- Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)

- Files in This Item:
- There are no files associated with this item.