created with NetLogo

view/download model file: GraphColoring2.nlogo

WHAT IS IT?

This is a model of graph coloring


HOW IT WORKS

Each node looks around and chooses a color that is least popular with its neighbors. If there are multiple color options with the same minimum number of neighbors, the node picks one of the colors.

HOW TO USE IT

Pick a topology: small world or growth. For the small world topology, you can choose the probability of rewiring a link (or rather, adding a random link on top of the lattice topology). For the growth model you can choose random (gamma = 1) or preferential (gamma = 0) attachment or something in between.

THINGS TO TRY

Try varying the topology. How does the probability of rewiring affect the speed to convergence (the process is random, and so it will take many averaged trials for an effect to emerge). Also try going between random and preferential attachment. How does this affect speed to convergence?

RELATED MODELS

See other models in the Networks section of the Models Library, such as Giant Component and Preferential Attachment. Also check out Lada's other NetLogo models:
http://projects.si.umich.edu/netlearn


CREDITS AND REFERENCES

This model was adapted from: Wilensky, U. (2005). NetLogo Small Worlds model. http://ccl.northwestern.edu/netlogo/models/SmallWorlds. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

It was written by Lada Adamic, 2008