کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656792 1632981 2015 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Subdivisions of a large clique in C6C6-free graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Subdivisions of a large clique in C6C6-free graphs
چکیده انگلیسی

Mader conjectured that every C4C4-free graph has a subdivision of a clique of order linear in its average degree. We show that every C6C6-free graph has such a subdivision of a large clique.We also prove the dense case of Mader's conjecture in a stronger sense, i.e., for every c  , there is a c′c′ such that every C4C4-free graph with average degree cn1/2cn1/2 has a subdivision of a clique KℓKℓ with ℓ=⌊c′n1/2⌋ℓ=⌊c′n1/2⌋ where every edge is subdivided exactly 3 times.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 112, May 2015, Pages 18–35
نویسندگان
, , ,