2001/07/11 by Pontus Svenson, Svenson, Pontus
Computer Science · Economics, Econometrics and Finance · Physics and Astronomy · #Complex Network Analysis Techniques #Computational Complexity (cs.CC) #Economic and Technological Innovation #F.2.m #FOS: Computer and information sciences #FOS: Physical sciences #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0107015
4 pages, 6 figures
arxiv created 2001/07/11 · openalex publication_date 2001/07/11 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note, we present results for the colouring problem on small world graphs created by rewiring square, triangular, and two kinds of cubic (with coordination numbers 5 and 6) lattices. As the rewiring parameter p tends to 1, we find the expected crossover to the behaviour of random graphs with corresponding connectivity. However, for the cubic lattices there is a region near p=0 for which the graphs are colourable. This could in principle be used as an additional heuristic for solving real world colouring or scheduling problems. Small worlds with connectivity 5 and p ~ 0.1 provide an interesting ensemble of graphs whose colourability is hard to determine. For square lattices, we get good data collapse plotting the fraction of colourable graphs against the rescaled parameter parameter p N-ν with ν= 1.35. No such collapse can be obtained for the data from lattices with coordination number 5 or 6.