Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. On subgraphs of C-2k-free graphs and a problem of Kuhn and Osthus
 
research article

On subgraphs of C-2k-free graphs and a problem of Kuhn and Osthus

Grosz, Daniel
•
Methuku, Abhishek  
•
Tompkins, Casey
May 1, 2020
Combinatorics Probability & Computing

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).

  • Details
  • Metrics
Type
research article
DOI
10.1017/S0963548319000452
Web of Science ID

WOS:000577595100004

Author(s)
Grosz, Daniel
Methuku, Abhishek  
Tompkins, Casey
Date Issued

2020-05-01

Published in
Combinatorics Probability & Computing
Volume

29

Issue

3

Start page

436

End page

454

Subjects

Computer Science, Theory & Methods

•

Mathematics

•

Statistics & Probability

•

Computer Science

•

chromatic number

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LCBIM  
Available on Infoscience
October 29, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/172878
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés