Minimizing unsatisfaction in colourful neighbourhoods

K.Y. Michael Wong, David Saad

Research output: Contribution to journalArticle

Abstract

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
Volume41
Issue number32
DOIs
Publication statusPublished - 30 Jul 2008

Fingerprint

Color
color
Population dynamics
Sparse Graphs
Coloring
Approximation
Finite Temperature
Population Dynamics
approximation
Colouring
constrictions
Connectivity
Restriction
thresholds
Zero
estimates
Vertex of a graph
Estimate
Temperature
temperature

Bibliographical note

© 2008 IOP Publishing Ltd.

Keywords

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

Cite this

@article{3d0206b36f7847a99c2b0e635d5bfc78,
title = "Minimizing unsatisfaction in colourful neighbourhoods",
abstract = "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.",
keywords = "colouring sparse graphs under various restrictions, nodes, neighbourhoods, analytical framework, tree approximation, solutions, population dynamics, threshold connectivity, transition",
author = "Wong, {K.Y. Michael} and David Saad",
note = "{\circledC} 2008 IOP Publishing Ltd.",
year = "2008",
month = "7",
day = "30",
doi = "10.1088/1751-8113/41/32/324023",
language = "English",
volume = "41",
pages = "324023",
journal = "Journal of Physics A: Mathematical and General",
issn = "0305-4470",
publisher = "IOP Publishing Ltd.",
number = "32",

}

Minimizing unsatisfaction in colourful neighbourhoods. / Wong, K.Y. Michael; Saad, David.

In: Journal of Physics A: Mathematical and General, Vol. 41, No. 32, 324023, 30.07.2008, p. 324023.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Minimizing unsatisfaction in colourful neighbourhoods

AU - Wong, K.Y. Michael

AU - Saad, David

N1 - © 2008 IOP Publishing Ltd.

PY - 2008/7/30

Y1 - 2008/7/30

N2 - 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.

AB - 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.

KW - colouring sparse graphs under various restrictions

KW - nodes

KW - neighbourhoods

KW - analytical framework

KW - tree approximation

KW - solutions

KW - population dynamics

KW - threshold connectivity

KW - transition

UR - http://www.scopus.com/inward/record.url?scp=52349084778&partnerID=8YFLogxK

U2 - 10.1088/1751-8113/41/32/324023

DO - 10.1088/1751-8113/41/32/324023

M3 - Article

VL - 41

SP - 324023

JO - Journal of Physics A: Mathematical and General

JF - Journal of Physics A: Mathematical and General

SN - 0305-4470

IS - 32

M1 - 324023

ER -