BROWSE

Related Scientist

Abhishek, Methuku's photo.

Abhishek, Methuku
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

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

Cited 0 time in webofscience Cited 0 time in scopus
57 Viewed 0 Downloaded
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)
URI
https://pr.ibs.re.kr/handle/8788114/8634
DOI
10.1017/S0963548319000452
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.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse