کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4666197 1633853 2013 35 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The chromatic thresholds of graphs
ترجمه فارسی عنوان
آستانه های رنگی نمودار
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات (عمومی)
چکیده انگلیسی

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
نویسندگان
, , , , ,