On subgraphs of C-2k-free graphs and a problem of Kuhn and Osthus
Let c denote the largest constant such that every C-6-free graph G contains a bipartite and C-4-free subgraph having a fraction c of edges of G. Gyori, Kensell and Tompkins showed that 3/8 <= c <= 2/5. We prove that c = 3/8. More generally, we show that for any epsilon > 0, and any integer k >= 2, there is a C-2k-free graph G' which does not contain a bipartite subgraph of girth greater than 2k with more than a fraction (1 - 1/2(2k-2)) 2/2k - 1 (1 + epsilon) of the edges of G'. There also exists a C-2k-free graph G '' which does not contain a bipartite and C-4-free subgraph with more than a fraction (1 - 1/2(k-1)) 1/k - 1 (1 + epsilon) of the edges of G ''. One of our proofs uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erdos. For any epsilon > 0, and any integers a, b, k >= 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 (1 - 1/b(a-1)) (1+e) 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 Kuhn and Osthus, which states that every bipartite C-2k-free graph G contains a C-4-free subgraph with at least a fraction 1/(k - 1) of the edges of G. We also answer a question of Kuhn and Osthus about C-2k-free graphs obtained by pasting together C-2l's (with k > l >= 3).
WOS:000577595100004
2020-05-01
29
3
436
454
REVIEWED