کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648301 1632430 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Vertex partitions of non-complete graphs into connected monochromatic kk-regular graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Vertex partitions of non-complete graphs into connected monochromatic kk-regular graphs
چکیده انگلیسی

In a landmark paper, Erdős et al. (1991) [3] proved that if GG is a complete graph whose edges are colored with rr colors then the vertex set of GG can be partitioned into at most cr2logrcr2logr monochromatic, vertex disjoint cycles for some constant cc. Sárközy extended this result to non-complete graphs, and Sárközy and Selkow extended it to kk-regular subgraphs. Generalizing these two results, we show that if GG is a graph with independence number α(G)=αα(G)=α whose edges are colored with rr colors then the vertex set of GG can be partitioned into at most (αr)c(αrlog(αr)+k)(αr)c(αrlog(αr)+k) vertex disjoint connected monochromatickk-regular subgraphs of GG for some constant cc.


► We study monochromatic partitions of non-complete graphs.
► We partition by monochromatic connected kk-regular subgraphs.
► We generalize earlier results.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issues 18–19, 6 October 2011, Pages 2079–2084
نویسندگان
, , ,