Minimizing unsatisfaction in colourful neighbourhoods

K.Y. Michael Wong, David Saad

    Research output: Contribution to journalArticlepeer-review


    Colouring sparse graphs under various restrictions is a theoretical problem of significant practical relevance. Here we consider the problem of maximizing the number of different colours available at the nodes and their neighbourhoods, given a predetermined number of colours. In the analytical framework of a tree approximation, carried out at both zero and finite temperatures, solutions obtained by population dynamics give rise to estimates of the threshold connectivity for the incomplete to complete transition, which are consistent with those of existing algorithms. The nature of the transition as well as the validity of the tree approximation are investigated.
    Original languageEnglish
    Article number324023
    Pages (from-to)324023
    Number of pages1
    JournalJournal of Physics A: Mathematical and General
    Issue number32
    Publication statusPublished - 30 Jul 2008

    Bibliographical note

    © 2008 IOP Publishing Ltd.


    • colouring sparse graphs under various restrictions
    • nodes
    • neighbourhoods
    • analytical framework
    • tree approximation
    • solutions
    • population dynamics
    • threshold connectivity
    • transition


    Dive into the research topics of 'Minimizing unsatisfaction in colourful neighbourhoods'. Together they form a unique fingerprint.

    Cite this