کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647899 1342382 2012 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Non-bipartite chromatic factors
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Non-bipartite chromatic factors
چکیده انگلیسی

The chromatic polynomial P(G,λ)P(G,λ) gives the number of proper colourings of a graph GG in at most λλ colours. If P(G,λ)=P(H1,λ)P(H2,λ)/P(Kr,λ)P(G,λ)=P(H1,λ)P(H2,λ)/P(Kr,λ), then GG is said to have a chromatic factorisation of order  rr with chromatic factors  H1H1 and H2H2. It is clear that, if 0≤r≤20≤r≤2, any H1⁄≅KrH1⁄≅Kr with chromatic number χ(H1)≥rχ(H1)≥r is the chromatic factor of some chromatic factorisation of order rr. We show that every H1⁄≅K3H1⁄≅K3 with χ(H1)≥3χ(H1)≥3, even when H1H1 contains no triangles, is the chromatic factor of some chromatic factorisation of order 33 and give a certificate of factorisation for this chromatic factorisation. This certificate shows in a sequence of seven steps using some basic properties of chromatic polynomials that a graph GG has a chromatic factorisation with one of the chromatic factors being H1H1. This certificate is one of the shortest known certificates of factorisation, excluding the trivial certificate for chromatic factorisations of clique-separable graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 6, 28 March 2012, Pages 1166–1170
نویسندگان
, ,