The graph colouring problem consists of assigning labels, or colours, to the vertices of a graph such that no two adjacent vertices share the same colour. In this work we investigate whether deep reinforcement learning can be used to discover a competitive construction heuristic for graph colouring. Our proposed approach, ReLCol, uses deep Q-learning together with a graph neural network for feature extraction, and employs a novel way of parameterising the graph that results in improved performance. Using standard benchmark graphs with varied topologies, we empirically evaluate the benefits and limitations of the heuristic learned by ReLCol relative to existing construction algorithms, and demonstrate that reinforcement learning is a promising direction for further research on the graph colouring problem.

本文探讨了深度强化学习在解决图着色问题中的应用，提出了一个名为ReLCol的构造启发式方法，该方法结合了深度Q学习和图神经网络，通过一种新颖方法对图进行参数化，相对现有的构造算法性能有所提升。在标准基准图上进行了实验证明了强化学习是进一步研究图着色问题的一个有前途的方向。

利用深度 Q 学习和图神经网络生成图着色启发式