کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646636 | 1342309 | 2016 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Local and global colorability of graphs
ترجمه فارسی عنوان
رنگ پذیری محلی و جهانی نمودارها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ پذیری محلی؛ عدد رنگی محلی؛ 2 انحطاط
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
It is shown that for any fixed c≥3c≥3 and rr, the maximum possible chromatic number of a graph on nn vertices in which every subgraph of radius at most rr is cc-colorable is Θ̃(n1r+1): it is O((n/logn)1r+1) and Ω(n1r+1/logn). The proof is based on a careful analysis of the local and global colorability of random graphs and implies, in particular, that a random nn-vertex graph with the right edge probability has typically a chromatic number as above and yet most balls of radius rr in it are 2-degenerate.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 428–442
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 428–442
نویسندگان
Noga Alon, Omri Ben-Eliezer,