Coloring random graphs and maximizing local diversity

Area of Science:

• Graph theory and network science
• Computational complexity and algorithms

Background:

• The graph coloring problem is fundamental in computer science and operations research.
• Random graphs with finite average connectivity present unique challenges for algorithmic solutions.

Purpose of the Study:

• To investigate a variation of the graph coloring problem on random graphs.
• To adapt and evaluate efficient algorithms for maximizing color diversity among neighboring vertices.
• To identify critical connectivity thresholds for achieving optimal solutions.

Main Methods:

• Adaptation of belief propagation and Walksat algorithms for the graph coloring variation.
• Experimental evaluation on two types of random graphs with varying system sizes.
• Analysis of algorithm performance and identification of critical connectivity values.

Main Results:

• Demonstrated the effectiveness of adapted belief propagation and Walksat algorithms.
• Identified a critical connectivity value essential for algorithms to find perfect solutions.
• Showcased the scalability and performance of the algorithms across different system sizes.

Conclusions:

• The adapted algorithms are efficient for solving this graph coloring variation on random graphs.
• The identified critical connectivity is a key factor for successful problem resolution.
• The problem and algorithms have practical implications for applications like distributed storage.