{"id":"arxiv/2607.09309","url":"https://arxiv.org/abs/2607.09309","tags":["cs.DS","cs.DM","math.CO","math.OC"],"score":0,"title":"A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting","domain":"cs.DS","source":"arxiv","authors":["Amir Ali Ahmadi","Pravesh K. Kothari","Yukai Tang"],"reviews":0,"subject":"cs.DS","summary":"We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perfect graph contains a clique of a given size by iteratively counting walks in the graph with certain weights assigned to its edges and nonedges. These weights are initialized according to a uniform scheme and then updated in each iteration based on the walk counts from the previous iteration.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}