Network Characters of Coloring Problems
Meng Zhu · 2004
Coloring Problem is a classical Constrain Satisfaction Problem. By analyzing the benchmark examples of Coloring Problem, characters are found, which are quite common in complex networks. In Small World networks, the average path lengths between each two nodes are small, while the whole system express high cluster tendency and the distributions of node degrees are skew. All these properties are lacked by Random Graphs, and thus we questioned completeness of the traditional method of utilizing random graph as benchmarks. Through the experimental results, the Least Coloring Number is found to have close relationships with the clustering coefficient of the network. With the raise of the clustering coefficient, the least coloring number increases exponentially.