کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647372 1632421 2014 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A dense set of chromatic roots which is closed under multiplication by positive integers
ترجمه فارسی عنوان
مجموعه ای متراکم از ریشه های کروماتیک که تحت ضرب با عدد صحیح مثبت بسته شده اند
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We study a very large family of graphs, the members of which comprise disjoint paths of cliques with extremal cliques identified. This broad characterisation naturally generalises those of various smaller families of graphs having well-known chromatic polynomials. We derive a relatively simple formula for an arbitrary member of the subfamily consisting of those graphs whose constituent clique-paths have at least one trivial extremal clique, and use this formula to show that the set of all non-integer chromatic roots of these graphs is closed under multiplication by natural numbers. A well-known result of Sokal then leads to our main result, which is that there exists a set of chromatic roots which is closed under positive integer multiplication in addition to being dense in the complex plane. Our findings lend considerable weight to a conjecture of Cameron, who has suggested that this closure property may be a generic feature of the chromatic polynomial. We also hope that the formula we provide will be of use to those computing with chromatic polynomials.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 321, 28 April 2014, Pages 45-52
نویسندگان
,