کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647298 1632414 2014 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on the real part of complex chromatic roots
ترجمه فارسی عنوان
یک یادداشت در قسمت واقعی ریشه های کروماتیک پیچیده
کلمات کلیدی
شماره کروماتیک، چندجملهای کروماتیک، ریشه های کروماتیک، بخش واقعی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A chromatic root is a root of the chromatic polynomial of a graph. While the real chromatic roots have been extensively studied and well understood, little is known about the real parts   of chromatic roots. It is not difficult to see that the largest real chromatic root of a graph with nn vertices is n−1n−1, and indeed, it is known that the largest real chromatic root of a graph is at most the tree-width of the graph. Analogous to these facts, it was conjectured in Dong et al. (2005) that the real parts of chromatic roots are also bounded above by both n−1n−1 and the tree-width of the graph.In this article we show that for all k≥2k≥2 there exist infinitely many graphs GG with tree-width kk such that GG has non-real chromatic roots zz with ℜ(z)>kℜ(z)>k. We also discuss the weaker conjecture and prove it for graphs GG with χ(G)≥n−3χ(G)≥n−3.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 328, 6 August 2014, Pages 96–101
نویسندگان
, ,