کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777116 1632570 2017 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On subgraphs of C2k-free graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On subgraphs of C2k-free graphs
چکیده انگلیسی

We show that for any ε>0, and any integer k≥2, there is a C2k-free graph G which does not contain a bipartite subgraph of girth greater than 2k with more than (1−122k−2)22k−1(1+ε) fraction of the edges of G. Győri et al. showed that if c denotes the largest constant such that every C6-free graph G contains a bipartite subgraph which is C4-free having c fraction of edges of G, then 38≤c≤25. Putting k = 3, our result implies that c=38.Our proof 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≥2, there exists an a-uniform hypergraph H of girth greater than k which does not contain any b-colorable subhypergraph with more than (1−1ba−1)(1+ε) fraction of the hyperedges of H.Kühn and Osthus showed that every bipartite C2l-free graph G contains a C4-free subgraph with at least 1/(l−1) fraction of the edges of G. We give a new and simple proof of this result. In the same paper Kühn and Osthus also showed that a C2l-free graph which is obtained by pasting together C4's has average degree at most 16l and asked whether there exists a number d=d(l) such that every C2l-free graph which is obtained by pasting together C2k's has average degree at most d if l>k≥3 are given integers. We answer this question negatively.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 521-526
نویسندگان
, , ,