کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328298 | 683931 | 2005 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On monochromatic component size for improper colourings
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On monochromatic component size for improper colourings On monochromatic component size for improper colourings](/preview/png/10328298.png)
چکیده انگلیسی
This paper concerns improper λ-colourings of graphs and focuses on the sizes of the monochromatic components (i.e., components of the subgraphs induced by the colour classes). Consider the following three simple operations, which should, heuristically, help reduce monochromatic component size: (a) assign to a vertex the colour that is least popular among its neighbours; (b) change the colours of any two adjacent differently coloured vertices, if doing so reduces the number of monochromatic edges; and (c) change the colour of a vertex, if by so doing you can reduce the size of the largest monochromatic component containing it without increasing the number of monochromatic edges. If a colouring cannot be further improved by these operations, then we regard it as locally optimal. We show that, for such a locally optimal 2-colouring of a graph of maximum degree 4, the maximum monochromatic component size is O(2(2log2n)1/2). The operation set (a)-(c) appears to be one of the simplest that achieves a o(n) bound on monochromatic component size. Recent work by Alon, Ding, Oporowski and Vertigan, and then Haxell, Szabó and Tardos, has shown that some algorithms can do much better, achieving a constant bound on monochromatic component size. However, the simplicity of our operation set, and of the associated local search algorithm, make the algorithm, and our locally optimal colourings, of interest in their own right.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 148, Issue 1, 30 April 2005, Pages 89-105
Journal: Discrete Applied Mathematics - Volume 148, Issue 1, 30 April 2005, Pages 89-105
نویسندگان
Keith Edwards, Graham Farr,