Premium
Four‐cycles in graphs without a given even cycle
Author(s) -
Kühn Daniela,
Osthus Deryk
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20048
Subject(s) - mathematics , combinatorics , chordal graph , discrete mathematics , graph
We prove that every bipartite C 2 l ‐free graph G contains a C 4 ‐free subgraph H with e ( H ) ≥ e ( G )/( l – 1). The factor 1/( l – 1) is best possible. This implies that ex( n , C 2 l ) ≤ 2( l – 1)ex( n , { C 4 , C 2 l }), which settles a special case of a conjecture of Erdős and Simonovits. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 147–156, 2005
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom