کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649959 1342471 2008 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Chromatic coloring with a maximum color class
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Chromatic coloring with a maximum color class
چکیده انگلیسی

Let GG be any graph, and also let Δ(G)Δ(G), χ(G)χ(G) and α(G)α(G) denote the maximum degree, the chromatic number and the independence number   of GG, respectively. A chromatic coloring   of GG is a proper coloring of GG using χ(G)χ(G) colors. A color class in a proper coloring of GG is maximum   if it has size α(G)α(G). In this paper, we prove that if a graph GG (not necessarily connected) satisfies χ(G)≥Δ(G)χ(G)≥Δ(G), then there exists a chromatic coloring of GG in which some color class is maximum. This cannot be guaranteed if χ(G)<Δ(G)χ(G)<Δ(G). We shall also give some other extensions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 23, 6 December 2008, Pages 5533–5537
نویسندگان
, , ,