Monash University
Browse

An Algorithm for finding 2-colourings with Small Monochromatic Components in Graphs of Maximum Degree 4

Download (121.89 kB)
report
posted on 2022-08-29, 05:06 authored by K Edwards, G E Farr
This paper concerns improper l-colourings of graphs in which all monochromatic components (i.e., components of the subgraphs induced by the colour classes) have at most C vertices. We present and analyse an efficient algorithm which finds, for any graph G of maximum degree 4, a 2-colouring in which all monochromatic components have size at most O(2(2 log_2 n)^{1/2}) and maximum degree at most 2. The algorithm is based on simply flipping the colour of a vertex whenever there is immediate gain from doing so, and so is greedy in some sense. An algorithm that achieves a constant bound (six) on monochromatic component size is implicit in recent work of Haxell, Szab\'o and Tardos, which in turn improves a result of Alon, Ding, Oporowski and Vertigan. However the simple greedy nature of our algorithm makes it an interesting object of study in its own right, and in fact our bound on monochromatic component size applies to any 2- colouring that (roughly) cannot be improved by a single vertex colour flip. We also define the metachromatic number of a class of graphs to be the minimum l such that, for some C, every graph in the class has a colouring of the above kind. We establish a lower bound of Floor(log2(d/2 + 1)) for the metachromatic number of the class of graphs of maximum degree at most d.

History

Technical report number

2002/122

Year of publication

2002

Usage metrics

    Monash Information Technology Technical Reports

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC