On monochromatic component size for improper colourings

Keith Edwards, Graham Farr

    Research output: Contribution to journalArticlepeer-review

    2 Citations (Scopus)


    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(2 log2 n)1/2 ). The operationset (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.
    Original languageEnglish
    Pages (from-to)89-105
    Number of pages17
    JournalDiscrete Applied Mathematics
    Issue number1
    Publication statusPublished - Apr 2005


    • Graph colouring
    • Graph partition
    • Monochromatic components
    • Metacolouring
    • Algorithm


    Dive into the research topics of 'On monochromatic component size for improper colourings'. Together they form a unique fingerprint.

    Cite this