کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4666197 | 1633853 | 2013 | 35 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The chromatic thresholds of graphs
ترجمه فارسی عنوان
آستانه های رنگی نمودار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات (عمومی)
چکیده انگلیسی
The chromatic threshold δχ(H)δχ(H) of a graph HH is the infimum of d>0d>0 such that there exists C=C(H,d)C=C(H,d) for which every HH-free graph GG with minimum degree at least d|G|d|G| satisfies χ(G)⩽Cχ(G)⩽C. We prove that δχ(H)∈{r−3r−2,2r−52r−3,r−2r−1} for every graph HH with χ(H)=r⩾3χ(H)=r⩾3. We moreover characterise the graphs HH with a given chromatic threshold, and thus determine δχ(H)δχ(H) for every graph HH. This answers a question of Erdős and Simonovits [P. Erdős, M. Simonovits, On a valence problem in extremal graph theory, Discrete Math. 5 (1973), 323–334], and confirms a conjecture of Łuczak and Thomassé [Tomasz Łuczak, Stéphan Thomassé, Colouring dense graphs via VC-dimension, arXiv:1011.4310 (submitted for publication)].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Mathematics - Volume 235, 1 March 2013, Pages 261–295
Journal: Advances in Mathematics - Volume 235, 1 March 2013, Pages 261–295
نویسندگان
Peter Allen, Julia Böttcher, Simon Griffiths, Yoshiharu Kohayakawa, Robert Morris,